Problem:


Score : 300 points

Problem Statement

Gotou just received a dictionary. However, he doesn't recognize the language used in the dictionary. He did some analysis on the dictionary and realizes that the dictionary contains all possible diverse words in lexicographical order.

A word is called diverse if and only if it is a nonempty string of English lowercase letters and all letters in the word are distinct. For example, atcoder, zscoder and agc are diverse words while gotou and connect aren't diverse words.

Given a diverse word S, determine the next word that appears after S in the dictionary, i.e. the lexicographically smallest diverse word that is lexicographically larger than S, or determine that it doesn't exist.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

1 \leq |S| \leq 26

S is a diverse word.

Input

Input is given from Standard Input in the following format:

S

Output

Print the next word that appears after S in the dictionary, or -1 if it doesn't exist.

Sample Input 1

atcoder

Sample Output 1

atcoderb

atcoderb is the lexicographically smallest diverse word that is lexicographically larger than atcoder. Note that atcoderb is lexicographically smaller than b.

Sample Input 2

abc

Sample Output 2

abcd

Sample Input 3

zyxwvutsrqponmlkjihgfedcba

Sample Output 3

-1

This is the lexicographically largest diverse word, so the answer is -1.

Sample Input 4

abcdefghijklmnopqrstuvwzyx

Sample Output 4

abcdefghijklmnopqrstuvx



Sample input:
atcoder


Sample output:
atcoderb

Submission status: Accepted

Solution code:
s = input()

dic = "abcdefghijklmnopqrstuvwxyz"

if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)

elif len(s) < 26:
    t = ""
    for x in dic:
        if s.count(x) == 0:
            t = x
            break
    print(s+t)
else:
    for idx,x in enumerate(s):
        t = s[-idx-1]
        l = s[-idx-1:]
        min_s = ""
        for y in l:
            if t < y:
                min_s = y if min_s=="" else min(min_s, y)
        
        if min_s != "":
            break
    print(s[:-idx-1]+min_s)

Submission status: Accepted

Solution code:
import string

s = input()

if len(s) != 26:
  mins = min(set(string.ascii_lowercase) - set(s))
  print(s + mins)
else:
  is_re = True
  for i, (nexts, prevs) in enumerate(zip(s[::-1], s[::-1][1:])):
    if nexts > prevs:
      is_re = False
      break

  if is_re:
    print(-1)
  else:
    minq = None
    for _s in s[26-i-1:]:
      if minq is None:
        minq = _s
      else:
        if _s > s[26-i-2] and minq > _s:
          minq = _s
    print(s[:26-i-2] + minq)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
l = [0 for i in range(26)]
if N < 26:
    for i in range(N):
        l[ord(S[i])-97] += 1
    for i in range(26):
        if l[i] == 0:
            print(S+str(chr(i+97)))
            break
elif S == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
else:
    m = 0
    for i in reversed(range(26)):
        if m > ord(S[i])-97:
            id = i
            break
        m = ord(S[i])-97
    for i in range(id,26):
        l[ord(S[i])-97] += 1
    for i in range(len(l)):
        if l[i] == 1 and ord(S[id])-97 < i:
            s = chr(i+97)
            break
    print(S[:id]+str(s))

Submission status: Accepted

Solution code:
S = input()
A = "abcdefghijklmnopqrstuvwxyz"
if len(S)<26:
    for c in A:
        if c not in S:
            print(S+c)
            break
elif S=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    for i in range(24,-1,-1):
        for c in A:
            if c not in S[:i] and c>S[i]:
                print(S[:i]+c)
                break
        else:
            continue
        break

Submission status: Accepted

Solution code:
import sys
s = input()
L = []
alp = [chr(ord('a') + i) for i in range(26)]
TF = [False]*26
for i in range(len(s)):
  if not s[i] in L:
    L.append(s[i])
    TF[ord(s[i])-97] = True
if len(L) != 26:
  for i in range(26):
    if TF[i] == False:
      k = alp[i]
      break
  print(s+k)
else:
  right = s[-1]
  for i in reversed(range(len(s))):
    k = s[i]
    if k < right:
      for j in range(ord(k),ord(k)+26):
        if chr(j) in s[i+1:]:
          print(s[:i]+chr(j))
          break
      sys.exit()
    else:
      right = max(k,right)
  print(-1)

Submission status: Accepted

Solution code:
S = input()
N = len(S)

if N < 26:
    for i in range(97, 123):
        if chr(i) not in S:
            print(S + chr(i))
            exit()

min_c = [S[-1]]
for c, i in zip(S[-2::-1], range(24, -1, -1)):
    for mc in min_c:
        if c < mc:
            print(S[:i] + mc)
            exit()
    else:
        min_c.append(c)
        min_c.sort()
print(-1)

Submission status: Accepted

Solution code:
s = input()
l = list('abcdefghijklmnopqrstuvwxyz')
for s_ in s:
    l.remove(s_)
if l==[]:
    l.append(s[-1])
    for i in range(len(s)-2,-1,-1):
        if s[i]<max(l):
            for k in l:
                if k>s[i]:
                    print(s[:i]+k)
                    exit()
        l.append(s[i])
    print(-1)
else:
    print(s+l[0])

Submission status: Accepted

Solution code:
import numpy as np
alpha = list('abcdefghijklmnopqrstuvwxyz')
alpha_num = [num for num in range(26)]

d = {char:num for (char, num) in zip(alpha, range(26))}

S = input()
S_num = np.array([d[char] for char in S])
last = S_num[-1]

flag = True

if len(S) < 26:
  S_num.sort()
  for k in range(len(S_num)):
    if S_num[k] != alpha_num[k]:
      print(S + alpha[k])
      flag = False
      break
  if flag:
    print(S + alpha[len(S)])

else:
  for k in reversed(range(1, 26)):
    if S_num[k] > S_num[k-1]:
      A = S_num[k:]
      A = A[A > S_num[k-1]]
      A.sort()
      print(S[:k-1] + alpha[A[0]])
      flag = False
      break
  if flag:
    print(-1)

Submission status: Accepted

Solution code:
S = input()

alph = [0] * 26

for index, i in enumerate(S):
    pointer = ord(i) - ord("a")
    alph[pointer] += 1


if(len(S) == 26):
    if(S=="zyxwvutsrqponmlkjihgfedcba"):
        print(-1)
        exit()
    else:
        old=""
        for i, s1 in enumerate(S[::-1]):
            if i != 0 and s1 < old[-1]:
                out = S[:len(S)-i-1] + min([o for o in old if o > s1])
                print(out)
                exit()
            old += s1
        
else:
    for i in range(26):
        if(alph[i]==0):
            print(S+chr(i+ord("a")))
            exit()

Submission status: Accepted

Solution code:
s=input()
last='zyxwvutsrqponmlkjihgfedcba'
if s==last:print(-1);exit()
d={c for c in s}
lest={c for c in last}-d
if len(lest)>0:print(s+sorted(lest)[0]);exit()
m=[s[-1]]
for i in range(25)[::-1]:
  for n in sorted(m):
    if s[i]<n:print(s[:i]+n);exit()
  m+=[s[i]]

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import heapq
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    s = SI()

    ss = [ord(c) for c in s]
    abc = [ord(c) for c in 'abcdefghijklmnopqrstuvwxyz']
    if len(s) < 26:
        sss = set(ss)
        for c in abc:
            if c not in sss:
                return s + chr(c)
    hq = []
    prev = ss[-1]
    for i in range(len(s))[::-1]:
        c = ss[i]
        if c >= prev:
            heapq.heappush(hq, c)
        else:
            while hq and hq[0] < c:
                heapq.heappop(hq)
            return s[:i] + chr(hq[0])
        prev = c

    return -1


print(main())

Submission status: Accepted

Solution code:
S = input()
A = [chr(i) for i in range(ord("a"),ord("z")+1)]

if len(S) < 26 :
    for i in range(len(A)) :
        if A[i] not in S :
            ans = S + A[i]
            break
elif S == "".join(A[::-1]) :
    ans = -1
else :
    B = []
    for i in range(len(A)-1) :
        right = S[len(A)-1-i]
        left = S[len(A)-1-(i+1)]
        B.append(right)
        if left < right:
            last = "z"
            for b in B :
                if left > b :
                    continue
                last = min(last,b)
            ans = S[:len(S)-1-(i+1)] + last
            break
print(ans)

Submission status: Accepted

Solution code:
s=input()
b="abcdefghijklmnopqrstuvwxyz"
from collections import defaultdict 
if len(s)<26:
  d=defaultdict(int)
  for c in s:
    d[c]+=1
  for bb in b:
    if d[bb]==0:
      print(s+bb)
      exit() 
N=len(s)
lst=[]
for first in range(N-1,0,-1):
  mn=s[first]
  for i in range(first-1,-1, -1):
    if s[i]<mn:
      lst.append(s[:i]+mn)
      #print(s[:i]+mn)
      #exit()
if lst:
  print(sorted(lst)[0])
  exit()
print(-1)

Submission status: Accepted

Solution code:
s = input()

if len(s) != 26:
    se = set([])
    for w in s:
        se.add(w)

    for i in range(26):
        w = chr(ord('a')+i)
        if w not in se:
            print(s + w)
            exit()

if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

se = set([])
for i in reversed(range(26)):
    se.add(s[i])
    for j in range(ord(s[i])-ord('a')+1, 26):
        if chr(ord('a')+j) in se:
            print(s[:i]+chr(ord('a')+j))
            exit()

Submission status: Accepted

Solution code:
S = input()
if len(S) < 26:
    for i in range(26):
        c = chr(ord('a')+i)
        if c not in S:
            print(S + c)
            exit()
if S == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
    exit()

cs = set()
for i in range(25):
    t,tt = S[-i-1],S[-i-2]
    cs.add(t)
    if tt < t:
        last = 'z'
        for c in cs:
            if c < tt: continue
            last = min(last, c)
        print(S[:-i-2] + last)
        exit()

Submission status: Accepted

Solution code:
import string

alp = string.ascii_lowercase

def main():
    s = input()
    if len(s) < 26:
        for i in alp:
            if i not in s:
                print (s + i)
                return
    if s == alp[::-1]:
        print(-1)
        return
    L = len(s)
    tmp = []
    tt = ''
    for i, ss in enumerate( s ):
        tmp += [ s[L-i-1] ]
        if s[L-i-1] > s[L-i-2]:
            ans = s[:L-i-2]
            tt = s[L-i-2] 
            break
    tmp.sort()
    for i in tmp:
        if i > tt:
            print (ans + i)
            break
main()

Submission status: Accepted

Solution code:
S = input()

if S == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
    exit()

tmp = {a: 0 for a in 'abcdefghijklmnopqrstuvwxyz'}

for x in S:
    tmp[x] += 1

tmp2 = []
if all(x == 1 for x in tmp.values()):
    for i in range(len(S)-1, 0, -1):
        tmp2.append(S[i])
        if S[i-1] < S[i]:
            tmp2 = [x for x in tmp2 if x > S[i-1]]
            print(S[:i-1]+min(tmp2))
            exit()
else:
    for k, v in tmp.items():
        if v == 0:
            tmp2.append(k)
    print(S+min(tmp2))

Submission status: Accepted

Solution code:
import string

alphabet = string.ascii_lowercase

S = input()
count = list(map(lambda x: S.count(x), alphabet))

# add the alphaebts
for a in alphabet:
    if count[alphabet.index(a)] == 0:
        print(S + a)
        exit()

count = [0 for _ in range(len(alphabet))]
cand = ""

# change the alphabets
for i, s in enumerate(S[::-1]):
    cand += s
    if i == len(S) - 1:
        print(-1)
        exit()
    res = ""
    for a in cand:
        if ord(S[-(i + 2)]) < ord(a):
            if res and res < S[: len(S) - i - 2] + a:
                exit
            else:
                res = S[: len(S) - i - 2] + a
    if res:
        print(res)
        exit()

Submission status: Accepted

Solution code:
S = input()
import sys

if S == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
    sys.exit(0)

atoz = list(map(chr,range(97,123)))
charmap = dict()
for c in atoz:
    charmap[c] = 0

for s in S:
    charmap[s] += 1

flag = 0
for c in atoz:
    if charmap[c] == 0:
        flag = 1
        S = S + c
        break

if flag == 0:
    index = 0
    for i in range(len(S)-1):
        if S[-1-i] > S[-2-i]:
            index = -2-i
            break
    tmp = sorted(list(S[index+1:]))
    for t in tmp:
        if t > S[index]:
            S = S[:index]+t
            break

print(S)

Submission status: Accepted

Solution code:
import bisect
S=input()

A=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
N=[0 for i in range(26)]
n=[i for i in range(26)]
a=[]

if S=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
elif len(S)<26:
    for i in range(len(S)):
        for j in range(26):
            if S[i]==A[j]:
                N[j]=1
    for i in range(26):
        if N[i]==0:
            S=S+A[i]
            print(S)
            exit()
else:
    S=list(S)
    for i in range(len(S)):
        for j in range(26):
            if S[i]==A[j]:
                S[i]=n[j]
    for i in range(25):
        if S[25-i]>S[24-i]:
            break
    L=S[25-i:]
    L.sort()
    X=S[:24-i]
    Y=L[bisect.bisect_left(L,S[24-i])]
    X.append(Y)
   
    for i in range(len(X)):
        for j in range(26):
            if X[i]==n[j]:
                X[i]=A[j]
    print("".join(X))

Submission status: Accepted

Solution code:
alphabet = "abcdefghijklmnopqrstuvwxyz"
S = raw_input()
if len(S) < 26:
  for ab in alphabet:
    if not ab in S:
      print S+ab
      break
else:
  i = -1
  s = "Z"
  while i > -27 and s < S[i]:
    s = S[i]
    i -= 1
  if i == -27:
    print "-1"
  else:
    for ab in alphabet[alphabet.index(S[i])+1:]:
      if not ab in S[:i]:
        print S[:i]+ab
        break

Submission status: Accepted

Solution code:
import collections
import itertools
import numpy as np
import sys
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()

abc = "abcdefghijklmnopqrstuvwxyz"
num = [i for i in range(26)]
dic = {"null":-1}
for i in range(26):
    dic[abc[i]] = num[i]+1

l = []
tmp = "null"
if len(s) == 26:
    for i in range(25,-1,-1):
        if dic[tmp] < dic[s[i]]:
            tmp = s[i]
            l.append(s[i])
        else:
            for j in l:
                if dic[j] < dic[s[i]]:
                    continue
                else:
                    print(s[:i]+j)
                    exit()
                    break
    else:
        print(-1)
else:
    for i in range(26):
        if abc[i] in s:
            continue
        else:
            print(s+abc[i])
            break

Submission status: Accepted

Solution code:
S = list(input())

D = list("abcdefghijklmnopqrstuvwxyz")

if len(S) == 26:
  cnt = 0
  L = []
  for i in range(25, -1, -1):
    Flag = True
    for j in range(cnt, 26):
      if S[i] == D[j]:
        L.append(S[i])
        cnt = j
        Flag = False
        break
    if Flag:
      L.sort()
      for k in L:
        if k > S[i]:
          S[i] = k
          break
      print("".join(S[:i + 1]))
      exit()
  print("-1")      
else:
  for i in S:
    D.remove(i)
  print("".join(S) + D[0])

Submission status: Accepted

Solution code:
import string
A=string.ascii_lowercase
S=input()
if S==A[::-1]:
    print(-1)
elif len(S)==26:
    i=-1
    while S[i-1]>S[i]:
        i-=1
    for j in range(-1,i-1,-1):
        if S[j]>S[i-1]:
            c=S[j]
            break
    print(S[:i-1]+c)
else:
    c=sorted(set(A)-set(S))[0]
    print(S+c)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import dropwhile

alphabet = set('abcdefghijklmnopqrstuvwxyz')

if __name__ == '__main__':
    s = input()
    l = [c for c in alphabet - set(s)]
    if l != []:
        print(s + min(l))
        quit(0)

    deq = deque()
    deq.append(s[-1])
    for i in range(24, -1, -1):
        if s[i] < s[i + 1]:
            small = next(dropwhile(lambda c: c <= s[i], deq))
            print(s[:i] + small)
            quit(0)
        else:
            deq.append(s[i])

    print(-1)

Submission status: Accepted

Solution code:
S = input()
S = list(S)
li = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

for s in S:
    if s in li:
        li.remove(s)

if len(li) == 0:
    li = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    max = 26
    m = []
    for i in range(2,len(S)+1):
        m.append(li.index(S[-i+1]))
        if li.index(S[-i]) < li.index(S[-i+1]):
            m = [x for x in m if x > li.index(S[-i])]
            S[-i] = li[min(m)]
            S = S[:-i+1]
            for s in S:
                print(s,end='')
            exit()
    print(-1)
else:
    S += li[0]
    for s in S:
        print(s,end='')

Submission status: Accepted

Solution code:
import bisect
ss = input()
ss =list(map(ord, ss))
dic = [i for i in range(97,123)]
# print(dic)
for s in ss:
    dic.remove(s)
# print(dic)
if len(ss)<26:
    ss.append(min(dic))
else:
    for s in ss[::-1]:
        if len(dic)>0 and s < max(dic):
            ss[ss.index(s)] = dic[bisect.bisect_right(dic,s)]
            break
        dic.append(ss.pop(ss.index(s)))
        dic = sorted(dic)
    else:
        ss = -1
print(ss if ss == -1 else ''.join(list(map(chr,ss))))

Submission status: Accepted

Solution code:
S = input()
 
chars = "abcdefghijklmnopqrstuvwxyz"
char_set = set(chars)
 
if len(S) == 26:
    for i in range(len(S)-1, -1, -1):
        x = chars.index(S[i])
        y = sorted(set(chars[x+1:])-set(S[:i]))
        # print(i, y)
        if len(y):
            print(S[:i]+y[0])
            exit()
else:
    t = sorted(set(chars)-set(S))[0]
    print(S+t)
    exit()
print(-1)

Submission status: Accepted

Solution code:
N = list(input())
setN = set(N)
D = list('abcdefghijklmnopqrstuvwxyz')
if len(N) < 26:
    for d in D:
        if not d in setN:
            N.append(d)
            print(''.join(N))
            exit()
else:
    N.reverse()
    for i in range(25):
        if N[i] < N[i+1]:
            continue
        else:
            tmp = N[i+1]
            ans = N[i+2:]
            ans.reverse()
            for n in N[:i+2]:
                if ord(n) - ord(tmp) > 0:
                    ans.append(n)
                    print(''.join(ans))
                    exit()
print(-1)

Submission status: Accepted

Solution code:
N = list(input())
setN = set(N)
D = list('abcdefghijklmnopqrstuvwxyz')
rD = list('zyxwvutsrqponmlkjihgfedcba')
if len(N) < 26:
    for d in D:
        if not d in setN:
            N.append(d)
            print(''.join(N))
            exit()
else:
    N.reverse()
    for i in range(25):
        if N[i] < N[i+1]:
            continue
        else:
            tmp = N[i+1]
            ans = N[i+2:]
            ans.reverse()
            cand = N[:i+2]
            cand.sort()
            for n in N[:i+2]:
                if ord(n) - ord(tmp) > 0:
                    ans.append(n)
                    print(''.join(ans))
                    exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def is_tasai(S):
    appare_set = set([])
    for s in S:
        if s in appare_set:
            return False
        appare_set.add(s)
    return True

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    S = input_raw[0]
    appare_set = set([])
    z_pos = 0
    for i in range(len(S)):
        if S[i] == "z":
            z_pos = i
        appare_set.add(S[i])

    not_appare = -1
    for s in range(ord("a"), ord("z") + 1):
        if chr(s) not in appare_set:
            print S + chr(s)
            return
    for i in range(len(S) - 1, -1, -1):
        new_s = chr(ord(S[i]) + 1)
        while new_s <= "z":
            S = S[:i]
            S += new_s
            if is_tasai(S) == True:
                print S
                return
            new_s = chr(ord(new_s) + 1)
        S = S[:i]
    print -1



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import string
chars = string.ascii_lowercase
def solve(S):
    if S == chars[::-1]:
        return -1
    for c in chars:
        if c in S:
            continue
        else:
            return S + c
    S = S[::-1]
    for i, c in enumerate(S):
        if i == len(S) - 1:
            continue
        c = S[i + 1]
        ans = S[i + 2:]
        if c == chars[-1]:
            continue
        n = chars[chars.find(c) + 1]
        while n in ans:
            if n == chars[-1]:
                n = -1
                break
            n = chars[chars.find(n)+1]
        if n == -1:
            continue

        ans = ans[::-1]
        ans += n
        return ans
    return -1

if __name__ == "__main__":
    print(solve(input()))

Submission status: Accepted

Solution code:
S = input()

chars = "abcdefghijklmnopqrstuvwxyz"
char_set = set(chars)

if len(S) == 26:
    for i in range(len(S)-1, -1, -1):
        x = chars.index(S[i])
        y = sorted(set(chars[x+1:])-set(S[:i]))
        # print(i, y)
        if len(y):
            print(S[:i]+y[0])
            exit()
else:
    t = sorted(set(chars)-set(S))[0]
    print(S+t)
    exit()
print(-1)

Submission status: Accepted

Solution code:
s = input()

alp = [0]*26
a_int = ord('a')

ans = -1
cand = []
if len(s) == 26:
    for i in reversed(range(1, 26)):
        if s[i] < s[i-1]:
            cand.append(s[i])
            continue
        else:
            cand.append(s[i])
            cand = sorted(cand, reverse=True)
            c = min(list(filter(lambda x: x > s[i-1], cand)))
            ans = s[0:i-1]+c
            break

else:
    for c in s:
        alp[ord(c)-a_int] = 1

    for i in range(26):
        if alp[i] == 0:
            ans = s+chr(i+a_int)
            break
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, initial=1)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()
N = len(S)

c = Counter(S)
if N < 26:
    for s in ascii_lowercase:
        if s not in c:
            print(S + s)
            exit()
else:
    # プレフィックスを1つずつ短くして試していく
    for i in range(N-1, -1, -1):
        pref = S[:i]
        S2 = S[i:]
        # 降順並び替え
        S3 = ''.join(sorted(S2, reverse=True))
        # 動かしたい場所が降順に並んでいたらもう動かせない
        if S2 != S3:
            # 交換対象の中で、置き換える文字より1つ大きいもの
            print(pref + S3[S3.index(S2[0])-1])
            exit()
    print(-1)

Submission status: Accepted

Solution code:
s = input()
alpha = "abcdefghijklmnopqrstuvwxyz"
tmpset = set()
n = len(s)
if n != 26:
    for i in range(n):
        tmpset.add(s[i])
    for i in range(26):
        if alpha[i] not in tmpset:
            s = s + alpha[i]
            print(s)
            exit()
else:
    if s == "zyxwvutsrqponmlkjihgfedcba":
        print(-1)
    else:
        for i in range(n - 1, 0, -1):
            if s[i] > s[i - 1]:
                tmpset.add(s[i])
                for j in range(26):
                    if alpha[j] in tmpset:
                        if s[i - 1] < alpha[j]:
                            s = s[:i - 1] + alpha[j]
                            print(s)
                            exit()
            else:
                tmpset.add(s[i])

Submission status: Accepted

Solution code:
import sys
s = input() + chr(96)

for j in range(len(s) - 1, -1, -1):
    sets = set(list(s[:j]))
    for i in range(ord(s[j]) + 1, ord('z') + 1):
        if chr(i) not in sets:
            print(s[:j] + chr(i))
            sys.exit(0)
print(-1)

Submission status: Accepted

Solution code:
n=input()
a=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
if n=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    if len(n)==26:
        q=a.index(n[-1])
        c=0
        d=[n[-1]]
        for i in range(24,-1,-1):
            c+=1
            d.append(n[i])
            d.sort()
            if d.index(n[i])<len(d)-1:
                print(n[:26-c-1]+d[d.index(n[i])+1])
                break
    else:
        for i in range(len(n)):
            a.pop(a.index(n[i]))
        print(n+a[0])

Submission status: Accepted

Solution code:
s=list(input())
al=[chr(ord('a') + i) for i in range(26)]
al=[i for i in al if i not in s]
if al:
    print(''.join(s)+al[0])
    exit()
for i in range(25,0,-1):
    if s[i-1]<s[i]:
        a=[j for j in s[i-1:] if s[i-1]<j]
        s=s[:i-1]+[sorted(a)[0]]
        print(''.join(s))
        break
        exit()
else:print(-1)

Submission status: Accepted

Solution code:
S = input()

string = 'abcdefghijklmnopqrstuvwxyz'
r_string = 'zyxwvutsrqponmlkjihgfedcba'

string = list(string)

if len(S)<26:
    
    for i in range(len(S)):
        for j in range(len(string)):
            if S[i]==string[j]:
                del string[j]
                break
    
    print(S+string[0])
elif S==r_string:
    print(-1)
else:
    for i in range(24, -1, -1):
        if S[i]<S[i+1]:
            end = i
            break
        
    now = S[end+1]
    th = S[end]
    
    for i in range(end+2, 26):
        if th<S[i]:
            if S[i]<now:
                now = S[i]
                
    print(S[0:end]+now)

Submission status: Accepted

Solution code:
def num(s):
    return ord(s) - ord("a")

S = input()

used = [False] * 26

for s in S:
    used[num(s)] = True

if len(S) != 26:
    for i in range(26):
        if not used[i]:
            ans = S + chr(ord("a") + i)
            break
    print(ans)
else:
    if S == "zyxwvutsrqponmlkjihgfedcba":
        print(-1)
    else:
        for i in range(len(S) - 1, -1, -1):
            s = S[i]
            used[num(s)] = False
            isOk = False
            for j in range(num(s) + 1, 26, 1):
                if not used[j]:
                    isOk = True
                    last = j
                    break
            if isOk:
                ans = S[:i] + chr(ord("a") + j)
                print(ans)
                break

Submission status: Accepted

Solution code:
def swapeds(s,a,b):
    return s.translate(str.maketrans({a:b,b:a}))
s = input()
arr = [1 for _ in range(26)]
ok = True
for i in s:
    if arr[ord(i)-97] > 0:
        arr[ord(i)-97] = 0
    else:
        ok = False
        break
mina = 25
for i in range(26):
    if arr[i] > 0 :
        mina = i
        break
        
if ok and s != 'zyxwvutsrqponmlkjihgfedcba':
    if len(s) < 26:
        print(s+chr(mina+97))
    else:
        for i in range(1,26)[::-1]:
            if s[i-1] < s[i]:
                tmp = s[i-1]
                maxs = 'z'
                break
        for i in range(s.index(tmp)+1,26)[::-1]:
            if tmp  < s[i] and maxs > s[i]:
                maxs = s[i]
        print(s[0:s.index(tmp)]+maxs)
else:
    print(-1)

Submission status: Accepted

Solution code:
# coding:utf-8


INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


s = input()
if s == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
    exit()

abc = 'abcdefghijklmnopqrstuvwxyz'
used = set()

ans = ''
if len(s) != 26:
    for c in abc:
        if c not in s:
            print(s + c)
            exit()

else:
    prev_c = ord(s[-1])
    candidate = []
    for i in range(25)[::-1]:
        curr = ord(s[i])
        next = ord(s[i + 1])
        if curr >= next:
            candidate.append(next)
        else:
            candidate.append(next)
            ct = ord('z')
            for c_int in candidate:
                if c_int < curr: continue
                ct = min(ct, c_int)
            print(s[:i] + chr(ct))
            exit()

Submission status: Accepted

Solution code:
S = input()

ans = ''

if len(S) != 26:
    a_z = [chr(i) for i in range(97, 123)]
    for s in S:
        a_z.remove(s)
    ans = S + a_z[0]
    print(ans)
else:
    if S == 'zyxwvutsrqponmlkjihgfedcba':
        ans = -1
        print(ans)
    else:
        a_z = [int(i) for i in range(97, 123)]
        inputs = list(map(ord, list(S)))
        buf = [inputs[-1]]
        for i in range(1, len(S)):
            if inputs[25-i] > inputs[25-(i-1)]:
                buf.append(inputs[25-i])
            else:
                buf.sort()
                for item in buf:
                    if inputs[25-i] < item:
                        last = item
                        break
                print(''.join(list(map(chr, inputs[:25-i]+[last]))))
                break

Submission status: Accepted

Solution code:
S=list(input())

chara=list("abcdefghijklmnopqrstuvwxyz")
chara_dic={}
for i in range(len(chara)):
	chara_dic[chara[i]]=i
chara_dic_2={}
for i in range(len(chara)):
	chara_dic_2[i]=chara[i]

count={}
for s in S:
	count[s]=count.get(s,0)+1

flag=0
if len(count)==len(chara):
	cur_chara=len(S)-1
	for pt in range(len(S)-2,-1,-1):
		if chara_dic[S[cur_chara]]<chara_dic[S[pt]]:
			cur_chara-=1
		else:
			flag=1
			ans=''
			for i in range(0,pt):
				ans+=str(S[i])
			ls=[]
			for i in range(pt+1,len(S)):
				if chara_dic[S[pt]]<chara_dic[S[i]]:
						ls.append(chara_dic[S[i]])
			ans+=chara_dic_2[min(ls)]
			break
else:
	flag=1
	ans=''
	for i in range(len(S)):
		ans+=S[i]
	for i in range(len(chara)):
		if chara[i] not in S:
			end=chara[i]
			break
	ans+=end

print(ans if flag else "-1")

Submission status: Accepted

Solution code:
S = input()
chars = list(map(lambda c: ord(c)-97, S))
if len(chars)!=26:
    chars = sorted(chars)
    i = 0
    while i==chars[i]:
        i += 1
        if i==len(chars):
            break
    ans = S + chr(i+97)
else:
    prev = -1
    i = 0
    for c in reversed(chars):
        if prev < c:
            i += 1
            prev = c
        else:
            break
    if i==26:
        ans = -1
    else:
        max_s = chars[-i-1]
        min_c = 27
        for c in chars[-i:]:
            if c>max_s and c<min_c:
                min_c = c
        ans = S[:-i-1] + chr(min_c+97)

print(ans)

Submission status: Accepted

Solution code:
a={chr(i) for i in range(ord("a"),ord("a")+26)}
s=input()
n=len(s)
if n<26:
  print(s+sorted(a-set(s))[0])
else:
  for i in range(2,27):
    if s[-i]<s[-i+1]:
      break
    if i==26:
      print(-1)
      exit()
  for j in sorted(s[-i+1:]):
    if j>s[-i]:break
  print(s[:-i]+j)