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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




L = "abcdefghijklmnopqrstuvwxyz"
invL = L[::-1]
S = S()
if len(S) != 26:
  for l in L:
    if l not in S:
      print(S+l)
      exit()
else:
  prev = chr(96)
  for s in S[::-1]:
    now = s
    if ord(now)<ord(prev):
      k = S.index(now)
      for l in L[ord(now)-97+1:]:
        if l not in S[:k]:
          print(S[:k]+l)
          exit()
    prev = now
  print(-1)

Solution (Python):
S = input()

s_sort = sorted(list(S))

new_character = "?"

if len(S) < 26:
  for  s in range(97,123,1):
    if S.count(chr(s))==0:
      new_character = chr(s)
      print(S + new_character)
      break
else:
  if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
  else:
    for x in range(25,0,-1):
      if ord(S[x-1]) < ord(S[x]):
        letters = sorted([ord(n) for n in list(S[x:])])
        letter = chr([l for l in letters if l >= ord(S[x-1])][0])
        ans = S[:x-1] + letter
        print(ans)
        break

Solution (Python):
s = input()
abc = [chr(i) for i in range(ord('a'), ord('z')+1)]

if len(s) == 26:
  for i in range(24, -1, -1):
    cand = list(s[i+1:])
    cand.sort()
    for c in cand:
      if ord(c) > ord(s[i]):
        print(s[:i] + c)
        exit()
  print(-1)
else:
  for l in abc:
    if l not in s:
      print(s + l)
      exit()

Solution (Python):
S = input()
alpha = "abcdefghijklmnopqrstuvwxyz"

if len(S) == 26:
    if S == alpha[::-1]:
        print(-1)
        exit()
    for i in reversed(range(25)):
        for j in reversed(range(i, 26)):
            if S[i] < S[j]:
                print(S[:i] + S[j])
                exit()
else:
    for x in alpha:
        if x not in S:
            print(S + x)
            break

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    S = input().strip()
    c = collections.Counter(S)

    for i in range(26):
        if c[chr(ord('a') + i)] == 0:
            print(S + chr(ord('a') + i))
            return

    for j in range(len(S) - 1, -1, -1):
        x = ord(S[j]) - ord('a')
        c[S[j]] -= 1
        for i in range(x + 1, 26):
            if c[chr(ord('a') + i)] == 0:
                print(S[:j] + chr(ord('a') + i))
                return

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
s = str(input())

if s == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
elif len(s) == 26:
    tmp = ord(s[-1])
    for i in range(len(s))[::-1]:
        if ord(s[i]) < tmp:
            ans = sorted(s[i:])
            for j in ans:
                if ord(j) > ord(s[i]):
                    print(s[:i] + j)
                    exit()
        tmp = ord(s[i])
else:
    alpha = [chr(i) for i in range(97, 97 + 26)]
    for i in alpha:
        if i not in s:
            print(s + i)
            break

Solution (Python):
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()
else:
    for i in reversed(range(1,26)):
        if s[i-1] < s[i]:
            s1 = s[0:i-1]
            for j in range(26):
                c = chr(ord("a")+j)
                if c > s[i-1] and c not in s1:
                    print(s1+c)
                    exit()
    print(-1)

Solution (Python):
s = str(input())

if s == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
elif len(s) == 26:
    tmp = ord(s[-1])
    for i in range(len(s))[::-1]:
        if ord(s[i]) < tmp:
            ans = sorted(s[i:])
            for j in ans:
                if ord(j) > ord(s[i]):
                    print(s[:i] + j)
                    exit()
        tmp = ord(s[i])
else:
    alpha = [chr(i) for i in range(97, 97 + 26)]
    for i in alpha:
        if i not in s:
            print(s + i)
            break

Solution (Python):
S = input()
if S == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
    exit()
import string
if len(S) < 26:
    tmp = sorted(list(set(list(string.ascii_lowercase))-set(list(S))))
    print(S+tmp[0])
    exit()
for i in range(26,-1,-1):
    tmp1 = S[:i]
    tmp2 = sorted(list(S[i:]))
    for t in tmp2:
        if S < tmp1+t:
            print(tmp1+t)
            exit()

Solution (Python):
s = input()
alpha = list("abcdefghijklmnopqrstuvwxyz")
if len(s) != 26:
    for ss in s:
        alpha.remove(ss)
    print(s + alpha[0])
else:
    if s == "zyxwvutsrqponmlkjihgfedcba":
        print(-1)
    else:
        tmp_pos = [[alpha.index(s[-1]), s[-1]]]
        for i, ss in enumerate(s[::-1], start = 1):
            for pos, tmp in tmp_pos:
                if alpha.index(ss) < pos:
                    print(s[:-i] + tmp)
                    exit()
            tmp = ss
            pos = alpha.index(ss)
            tmp_pos.append([pos, tmp])

Solution (Python):
S = input()
remaining = set("abcdefghijklmnopqrstuvwxyz") - set(S)
if remaining:
    print(S + min(remaining))
else:
    prev = S[25]
    for i in range(24, -1, -1):
        c = S[i]
        if c < prev:
            print(S[:i] + min(c for c in S[i + 1 :] if c > S[i]))
            break
        prev = c
    else:
        print(-1)

Solution (Python):
s = input()
al = [chr(i) for i in range(97, 97+26)]
l = list(s)
if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
elif len(s) == 26:
    for i in range(24, -1, -1):
        for j in range(25, i, -1):
            if s[i] < s[j]:
                print(s[:i] + s[j])
                exit()
else:
    for i in al:
        if not i in s:
            print(s + i)
            exit()

Solution (Python):
def next_diverse_word(s):
    alphabets = set(chr(ord('a') + i) for i in range(26))
    if s == 'zyxwvutsrqponmlkjihgfedcba':
        return -1
    r = alphabets - set(s)
    if len(r) != 0:
        return s + sorted(r)[0]
    s = list(s)
    r = [s[-1]]
    s = s[:-1]
    while True:
        k = s[-1]
        r.append(s[-1])
        s = s[:-1]
        t = [c for c in r if c > k]
        if len(t) != 0:
            s.append(sorted(t)[0])
            return ''.join(s)


S = input()
print(next_diverse_word(S))

Solution (Python):
import sys
S = input()

asc = [0]*26
for s in S:
    asc[ord(s)-97] = 1


if len(S) == 26:
    for i in range(26):
        for j in range(ord(S[25-i])-97,26): 
            if asc[j] == 0:
                print(S[:(25-i)]+chr(j+97))
                sys.exit()
        asc[ord(S[25-i])-97] = 0
    print(-1)
else:
    for i in range(26):
        if asc[i] == 0:
            S += chr(97+i)
            break
    print(S)

Solution (Python):
S = input()

flag = [0]*26

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

if len(S) < 26:
  for s in S:
    flag[ord(s)-ord('a')] = 1
  print(S + chr(flag.index(0)+ord('a')))
  
else:
  a = 0
  for i in range(len(S)-1,-1,-1):
    if a < ord(S[i]):
      flag[ord(S[i])-ord('a')] = 1
      a = ord(S[i])
    else:
      print(S[:i]+chr(flag[ord(S[i])-ord('a'):].index(1)+ord(S[i])))
      break

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    S = input().strip()
    if len(S) < 26:
        for i in range(97, 123):
            if chr(i) not in S:
                print(S + chr(i))
                return
    
    p = 0
    q = []
    for i, s in enumerate(S[::-1]):
        if ord(s) > p:
            p = ord(s)
            q.append(ord(s))
        else:
            min_ = 123
            for j in q:
                if j > ord(s):
                    min_ = min(min_, j)
            print(S[:-i-1] + chr(min_))
            return
    print('-1')

if __name__ == '__main__':
    main()

Solution (Python):
s = input()
k = 'abcdefghijklmnopqrstuvwxyz'
if len(s) < 26:
  for v in k:
    if not v in s:
      print(s+v)
      exit()
if s == k[::-1]:
  print(-1)
  exit()
for i in range(1,len(s)+1):
  t = s[-i:]
  if t != ''.join(sorted(t, reverse=True)):
    t = t[1:]
    break
for p in t[::-1]:
  if p > s[-i]:
    print(s[:-i]+p)
    exit()

Solution (Python):
s = input()

def set_char(data, c):
    for i in range(26):
        ret = chr(ord("a") + i)
        if ret not in data and ret > c:
            return ret

if len(s) < 26:
    data = set(s)
    for i in range(26):
        c = set_char(data, "")
    print(s + c)
else:
    i = len(s) - 1
    while i != 0 and s[i - 1] > s[i]:
        i -= 1
    if i == 0:
        print(-1)
    else:
        data = set(s[: i - 1])
        c = set_char(data, s[i - 1])
        print(s[: i - 1] + c)

Solution (Python):
from collections import Counter
def main():
    s = list(input())
    c = Counter(s)
    if len(s) != 26:
        for i in range(97, 123):
            if c[chr(i)] == 0:
                s.append(chr(i))
                print(''.join(s))
                exit()
            else:
                pass
    else:
        for i in range(1, 27):
            si = s[-i:]
            if si != sorted(si, reverse = True):
                ans = s[:-i]
                ans.append(min([sii for sii in si[1:] if sii > si[0]]))
                print(''.join(ans))
                break
        else:
            print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
def check():
    S = input()
    s_set = set(S)
    alpha = 'abcdefghijklmnopqrstuvwxyz'
    if len(S) == 26:
        if S == alpha[::-1]:
            return -1
        else:
            for i in range(1,len(S)+1):
                S1 = S[-i:]
                if S1 != ''.join(sorted(S1, reverse=True)):
                    S1 = S1[1:]
                    break
            for s in S1[::-1]:
                if s > S[-i]:
                    return S[:-i]+s
    else:
        for a in alpha:
            if a not in s_set:
                return S+a
print(check())

Solution (Python):
S = input()
s_set = set(S)
ind = len(S)

if len(S) == 26:
    if S == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
        exit()
    for i in range(24, -1, -1):
        if ord(S[i]) <= ord(S[i+1]):
            ind = i
            break
    ans = S[:ind]
    for s in reversed(S[ind+1:]):
        if ord(s) > ord(S[ind]):
            print(ans + s)
            exit()

else:        
    for i in range(26):
        if chr(i+97) in s_set:
            continue
        else:
            print(S + chr(i+97))
            break

Solution (Python):
from string import ascii_lowercase
def next_permutation(a):
    """Generate the lexicographically next permutation inplace.

    https://en.wikipedia.org/wiki/Permutation
    Return false if there is no next permutation.
    """
    
    
    for i in reversed(range(len(a) - 1)):
        if a[i] < a[i + 1]:
            break  
    else:  
        return -1  

    
    j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])
    
    return a[:i] + a[j]

s = input()
lower = set(ascii_lowercase)
for c in s:
    if c in lower:
        lower.remove(c)
    else:
        print(-1)
        exit()
if len(lower) > 0:
    lower = sorted(lower)
    print(s+lower[0])

else:
    print(next_permutation(s))

Solution (Python):
s = input()

NUM_OF_ALPHABETS = 26

usable = [True for x in range(NUM_OF_ALPHABETS)]

for c in s:
    usable[ord(c) - ord('a')] = False

for i in range(NUM_OF_ALPHABETS):
    if usable[i]:
        print(s + chr(ord('a') + i))
        exit()

for i in range(len(s))[::-1]:
    index = ord(s[i]) - ord('a')
    usable[index] = True
    for j in range(index+1, NUM_OF_ALPHABETS):
        if usable[j]:
            print(s[0:i] + chr(ord('a') + j))
            exit()
print(-1)

Solution (Python):
import sys
S = input()
if len(S)<26:
    for i in range(26):
        ans = S + chr(97+i)
        if len(ans) == len(list(set(ans))):
            print(ans)
            break
else:
    if S == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
    else:
        SS = S[0:-1]
        while True:
            SS = SS[0:-1]
            for i in range(26):
                ans = SS + chr(97+i)
                if len(ans) == len(list(set(ans))) and S < ans:
                    print(ans)
                    sys.exit()

Solution (Python):
S = list(input())

abc = [chr(ord('a') + i) for i in range(26)]

if len(S) < 26:
    rest_alp = list(set(abc) - set(S))
    rest_alp.sort()
    S.append(rest_alp[0])
    print("".join(S))
    exit()
else:
    for i in reversed(range(25)):
        for j in reversed(range(i+1, 26)):
            if S[i] < S[j]:
                ans = S[:i].append(S[j])
                print("".join(S[:i]) + "".join(S[j]))
                exit()
print(-1)

Solution (Python):
s = list(input())

ss = set(s)

if len(s) < 26:
    for c in "abcdefghijklmnopqrstuvwxyz":
        if c not in ss:
            print("".join(s) + c)
            exit()
else:
    suc = s[-1]
    while suc in ss and s:
        suco = ord(suc) + 1
        if suco > ord("z"):
            ss.remove(s.pop())
            if not ss:
                break
            suc = s[-1]
        else:
            suc = chr(suco)
    
    if not ss:
        print(-1)
    else:
        s[-1] = suc
        print("".join(s))

Solution (Python):
s = list(input())

ss = set(s)

if len(s) < 26:
    for c in "abcdefghijklmnopqrstuvwxyz":
        if c not in ss:
            print("".join(s) + c)
            exit()
else:
    suc = s[-1]
    while suc in ss and s:
        suco = ord(suc) + 1
        if suco > ord("z"):
            ss.remove(s.pop())
            if not ss:
                break
            suc = s[-1]
        else:
            suc = chr(suco)
    
    if not ss:
        print(-1)
    else:
        s[-1] = suc
        print("".join(s))

Solution (Python):
alp = "abcdefghijklmnopqrstuvwxyz"
s = input()
if len(s) < 26:
    for x in alp:
        if x not in s:
            print(s+x)
            break
elif s == alp[::-1]:
    print(-1)
else:
    
    for i in range(24,-1,-1):
        for j in range(25,i,-1):
            
            if s[i] < s[j]:
                print(s[:i] + s[j])
                exit()

Solution (Python):
s = str(input())
alpha = 'abcdefghijklmnopqrstuvwxyz'
inv_alpha = 'zyxwvutsrqponmlkjihgfedcba'
if len(s) == 26:
    if s == inv_alpha:
        print(-1)
    else:
        for i in reversed(range(25)):
            for j in reversed(range(i+1, 26)):
                if s[i] < s[j]:
                    print(s[:i] + s[j])
                    break
            else:
                continue
            break
else:
    S = sorted(set(alpha) - set(s))
    print(s + S[0])

Solution (Python):
def solve():
    S = input()
    
    if S == 'zyxwvutsrqponmlkjihgfedcba':
        return -1
    elif len(S) == 26:
        for i in range(26):
            for j in range(ord(S[-i-1])+1, 97+26):
                if chr(j) not in S[:-i-1]:
                    return S[:-i-1] + chr(j)
    else:
        for i in range(97, 97+26):
            if chr(i) not in S:
                return S+chr(i)
            
print(solve())

Solution (Python):
import sys
from collections import deque
s = deque(map(str, input().rstrip()))


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


s = [ord(x) for x in s]


if len(s) < 26:
    can_use = set(range(97, 123)) - set(s)
    s = s + [min(can_use)]


else:
    add = []
    s = s[::-1]
    prev = s[0]
    add.append(prev)

    
    if prev == 122:
        s[1] = 122
        s = s[::-1][:-1]

    
    
    else:
        for i in range(1, len(s)):
            if prev > s[i]:
                add = [x for x in add if x > s[i]]
                s[i] = (min(add))
                s = s[::-1][:-i]
                break
            prev = s[i]
            add.append(prev)


s = [chr(x) for x in s]

print("".join(s))

Solution (Python):
import sys
from collections import deque
s = deque(map(str, input().rstrip()))


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


s = [ord(x) for x in s]


if len(s) < 26:
    can_use = set(range(97, 123)) - set(s)
    s = s + [min(can_use)]


else:
    add = []
    s = s[::-1]
    prev = s[0]
    add.append(prev)

    
    if prev == 122:
        s[1] = 122
        s = s[::-1]
        s = s[:-1]

    
    
    else:
        for i in range(1, len(s)):
            if prev > s[i]:
                add = [x for x in add if x > s[i]]
                s[i] = (min(add))
                s = s[::-1]
                s = s[:-i]
                break
            prev = s[i]
            add.append(prev)


s = [chr(x) for x in s]

print("".join(s))

Solution (Python):
import sys
from collections import deque
s = deque(map(str, input().rstrip()))

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

s = [ord(x) for x in s]

if len(s) < 26:
    can_use = set(range(97, 123)) - set(s)
    s = s + [min(can_use)]

else:
    add = []
    s = s[::-1]
    prev = s[0]
    add.append(prev)

    if prev == 122:
        s[1] = 122
        s = s[::-1]
        s = s[:-1]

    else:
        for i in range(1, len(s)):
            if prev > s[i]:
                add = [x for x in add if x > s[i]]
                s[i] = (min(add))
                s = s[::-1]
                s = s[:-i]
                break
            prev = s[i]
            add.append(prev)

s = [chr(x) for x in s]

print("".join(s))

Solution (Python):
from copy import copy, deepcopy 












import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    def main():

        def next_permutation(a):
            """Generate the lexicographically next permutation inplace.

            https://en.wikipedia.org/wiki/Permutation
            Return false if there is no next permutation.
            """
            
            
            for i in reversed(range(len(a) - 1)):
                if a[i] < a[i + 1]:
                    break  
            else:  
                return False  

            
            j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])

            
            a[i], a[j] = a[j], a[i]

            
            a[i + 1:] = reversed(a[i + 1:])
            return True

        alpha = list(chr(ord('a')+i) for i in range(26))

        S = input()
        if len(S) < 26:
            for i in range(len(S)):
                alpha.remove(S[i])
            return S+alpha[0]
        else:
            S = list(S)
            P = S.copy()
            next_permutation(P)
            for i in range(26):
                if P[i] != S[i]:
                    return ''.join(P[:i+1])
            return -1
    print(main())

resolve()

Solution (Python):
from copy import copy, deepcopy












import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    def main():

        def next_permutation(a):
            """Generate the lexicographically next permutation inplace.

            https://en.wikipedia.org/wiki/Permutation
            Return false if there is no next permutation.
            """
            
            
            for i in reversed(range(len(a) - 1)):
                if a[i] < a[i + 1]:
                    break  
            else:  
                return False  

            
            j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])

            
            a[i], a[j] = a[j], a[i]

            
            a[i + 1:] = reversed(a[i + 1:])
            return True

        alpha = list(chr(ord('a')+i) for i in range(26))

        S = input()
        if len(S) < 26:
            for i in range(len(S)):
                alpha.remove(S[i])
            return S+alpha[0]
        else:
            S = list(S)
            P = S.copy()
            next_permutation(P)
            for i in range(26):
                if P[i] != S[i]:
                    return ''.join(P[:i+1])
            return -1
    print(main())

resolve()

Solution (Python):
from string import*;from itertools import*;b=ascii_lowercase;s=r=input();t=s[::-1];d=0
if len(s)>25:d=-[p*len(list(k))for p,k in groupby(i<j for i,j in zip(t,t[1:]))][0]-2;s,b,r=s[:d],s[d+1:],b[:ord((s*2)[d])-97]
print(-(d<-26)or s+sorted(set(b)-set(r))[0])

Solution (Python):
from string import*;from itertools import*;b=ascii_lowercase;s=r=input();t=s[::-1];d=0
if len(s)>25:d=-[p*len(list(k))for p,k in groupby([i<j for i,j in zip(t,t[1:])])][0]-2;s,b,r=s[:d],s[d+1:],b[:ord((s*2)[d])-97]
print(-(d<-26)or s+sorted(set(b)-set(r))[0])

Solution (Python):
from string import*;from itertools import*;b=ascii_lowercase;s=r=input();t=s[::-1];d=0
if len(s)>25:d=-[p*len(list(k))for p,k in groupby([i<j for i,j in zip(t,t[1:])])][0]-2;u=s*2;s,b,r=s[:d],s[d+1:],b[:ord(u[d])-97]
print(-(d<-26)or s+sorted(set(b)-set(r))[0])

Solution (Python):
A=input()
l=set(chr(ord('a') + i) for i in range(26))
l2=list(l-set(A))
l2.sort()
if len(A)!=26:
   print(A+l2[0])
else:
   for i in reversed(range(25)):
      for j in reversed(range(i+1,26)):
         if A[i] < A[j]:
            print(A[:i]+A[j])
            exit()
   else:
      print(-1)

Solution (Python):
from string import*;from itertools import*;b=ascii_lowercase;s=input();t=s[::-1]
if len(s)<26:print(s +sorted(set(b)-set(s))[0])
else:d=-[p*len(list(k))for p,k in groupby([i<j for i,j in zip(t,t[1:])])][0]-2;print(-(d<-26)or s[:d]+sorted(set(s[d+1:])-set(b[:ord(s[d])-97]))[0])

Solution (Python):
from string import*
from itertools import*
b = ascii_lowercase
s = input()
if len(s) < 26:
    print(s + sorted(set(b) - set(s))[0])
else:
    d = -[p*len(list(k)) for p, k in groupby([i < j for i, j in zip(s[-1::-1], s[-2::-1])])][0] - 2
    print(-(d < -26) or s[:d] + sorted(set(s[d+1:]) - set(b[:ord(s[d]) - 97]))[0])

Solution (Python):

from string import*
from itertools import*
b = ascii_lowercase
s = input()
l = len(s)
if l < 26:
    print(s + sorted(set(b) - set(s))[0])
else:
    t = s[::-1]
    a = [(p, len(list(k))) for p, k in groupby([i < j for i, j in zip(t, t[1:])])][0]
    d = - a[0]*a[1] - 2
    print(-(d < -26) or s[:d] + sorted(set(s[d+1:]) - set(b[:ord(s[d]) - 97]))[0])

Solution (Python):
s = input()
word = [0] * 26
for i in s:
    word[ord(i) - ord('a')] = 1

if sum(word) != 26:
    for i in range(26):
        if word[i] == 0:
            c = chr(i + ord('a'))
            break
    print(s + c)
    exit()
else:
    for i in range(25, -1, -1):
        if s[i] == 'z':
            pass
        else:
            now = ord(s[i]) + 1
            for j in range(now, ord('z') + 1):
                if not chr(j) in s[0:i]:
                    print(s[0:i] + chr(j))
                    exit()
print(-1)

Solution (Python):
s = input()
word = [0] * 26
for i in s:
    word[ord(i) - ord('a')] = 1

if sum(word) != 26:
    for i in range(26):
        if word[i] == 0:
            c = chr(i + ord('a'))
            break
    print(s + c)
else:
    if s == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
    else:
        for i in range(25, -1, -1):
            if s[i] == 'z':
                pass
            else:
                now = ord(s[i]) + 1
                for j in range(now, ord('z')+1):
                    if chr(j) in s[0:i]:
                        pass
                    else:
                        print(s[0:i] + chr(j))
                        exit()

Solution (Python):
s = input()
if len(set(s))==26:
    for i in range(26):
        for j in range(i+1):
            if s[-(i+1)]<s[-(j+1)]:
                print(s[:-(i+1)]+s[-(j+1)]);exit()
    else:
        print(-1);exit()
else:
    chr_li = [ord(chr_) for chr_ in s]
    for i in range(97,97+26):
        if i not in chr_li:
            print(s+chr(i));exit()

Solution (Python):
s = input()
l = len(s)

alf=set('abcdefghijklmnopqrstuvwxyz')
for i in range(l):
    if s[i] in alf:
        alf.remove(s[i])

if alf:
    t = list(alf)
    t.sort()
    s+=t[0]
else:
    stock=[]
    for i in range(1,26):
        if s[l-i-1]>s[l-i]:
            stock.append(s[l-i])
        else:
            stock.append(s[l-i])
            stock.sort()
            for j in stock:
                if j>s[l-i-1]:
                    s=s[:l-i-1]+j
                    print(s)
                    exit()
        if i==25:
            print('-1')
            exit()
print(s)

Solution (Python):
s=input()
t="abcdefghijklmnopqrstuvwxyz"
if s==t[::-1]:
  print(-1)
  exit(0)
if len(s)<26:
  for ti in t:
    if not ti in s:
      print(s+ti)
      exit(0)
else:
  for i in range(25):
    if s[-i-2]<s[-1-i]:
      t=s[:-i-2]
      u=sorted(list(s[-i-2:]))
      print(t+u[u.index(s[-2-i])+1])
      exit(0)

Solution (Python):
s = input()

if len(s) != 26:
    for c in range(ord('a'), ord('z')+1):
        c = chr(c)
        if not c in s:
            print(s+c)
            exit()
s = list(s)
t = []
while s:
    for c in t:
        if c > s[-1]:
            print(''.join(s[:-1])+c)
            exit()
    t.append(s.pop())

print('-1')

Solution (Python):
s=input()
if len(s)<26:
  for i in range(97,123):
    if not chr(i) in s:
      print(s+chr(i))
      exit()
else:
  for i in range(25)[::-1]:
    for j in range(i+1,26)[::-1]:
      if s[i]<s[j]:
        print(s[:i]+s[j])
        exit()
  else:
    print(-1)

Solution (Python):
S = input()
s = list(S)
o = [ord(x) for x in S]
alphabets = set([chr(i+97) for i in range(26)])
if len(S) < 26:
    used = set(s)
    unused = alphabets - used
    unusedo = [ord(x) for x in unused]
    print(''.join(S)+chr(min(unusedo)))
else:
    if S == 'zyxwvutsrqponmlkjihgfedcba':
        print('-1')
    else:
        diff = [ord(s[i+1]) - ord(s[i]) for i in range(25)]
        for i in range(1,26):
            if diff[-i] > 0:
                removed = S[:-i-1]
                current = S[-i-1]
                break
        usedr = set(list(removed)) | set(current)
        unusedr = alphabets - usedr
        unusedro = [ord(x) for x in unusedr if ord(x) > ord(current)]
        print(removed+chr(min(unusedro)))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = readline().rstrip().decode() + chr(96)
for i, ss in enumerate(s[::-1]):
    for m in range(ord(ss) + 1, 123):
        if chr(m) not in list(s[:-(i + 1)]):
            print(s[:-(i + 1)] + chr(m))
            exit()
print(-1)

Solution (Python):
import sys
s = input()
dic = "abcdefghijklmnopqrstuvwxyz"
for i in range(len(s),0,-1):
    for j in dic:
        if not j in s[:i]:
            if i == len(s):
                print(s[:i]+j)
                sys.exit()
            else:
                if dic.index(s[i]) < dic.index(j):
                    print(s[:i]+j)
                    sys.exit()
else:
    if s[0] != "z":
        print(dic[dic.index(s[0])+1])
    else:
        print(-1)

Solution (Python):
S = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"
if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    if len(S)<26:
        for a in alphabet:
            if a not in S:
                print(S + a)
                exit()
    else:
        ordmax = 0
        for n,s in enumerate(reversed(S)):
            if ordmax > ord(s):

                for j in range(alphabet.index(s)+1,26):
                    if alphabet[j] not in S[:-n-1] :
                        print(S[:-n-1] + alphabet[j])
                        exit()
            else:
                ordmax = max(ordmax,ord(s))