Problem: 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}.

Submission attempts (in order):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():

  
  l=['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']

  s=S()
  if s=='atcoder':
    exit()

  if s=='zyxwvutsrqponmlkjihgfedcba':
    return -1

  if len(s)!=26:
    for x in s:
      l.remove(x)
    return s+l[0]

  else:
    for i in range(1,len(s)):
      x=s[-i]
      for j in range(len(s)-i)[::-1]:
        if x>s[j]:
          return s[:j]+x

print(main())


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():

  
  l=['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']

  s=S()
  if s=='atcoder':
    exit()

  if s=='zyxwvutsrqponmlkjihgfedcba':
    return -1

  if len(s)!=26:
    for x in s:
      l.remove(x)
    return s+l[0]

  else:
    x=s[-1]
    for i in range(len(s)-1)[::-1]:
      if x>s[i]:
        return s[:i]

print(main())


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():

  
  l=['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']

  s=S()
  if s=='atcoder':
    exit()

  if s=='zyxwvutsrqponmlkjihgfedcba':
    return -1

  if len(s)!=26:
    for x in s:
      l.remove(x)
    return s+l[0]+l[0]

  else:
    x=s[-1]
    for i in range(len(s)-1)[::-1]:
      if x>s[i]:
        return s[:i]+x

print(main())


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():

  
  l=['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']

  s=S()
  if s=='atcoder':
    exit()

  if s=='zyxwvutsrqponmlkjihgfedcba':
    return -1

  if len(s)!=26:
    for x in s:
      l.remove(x)
    return s+l[0]

  else:
    x=s[-1]
    for i in range(len(s)-1)[::-1]:
      if x>s[i]:
        return s[:i]+x

print(main())


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


l=['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']

def main():
  s=S()
  if s=='zyxwvutsrqponmlkjihgfedcba':
    return -1

  for x in s:
    if l.count(x)==0:
      return -1
    l.remove(x)

  if len(l)>0:
    return ''.join(s)+l[0]

  nakama=[]
  for i in range(len(s))[::-1]:
    nakama.sort()
    b=s[i]
    for a in nakama:
      if a>b:
        return s[:i]+a
    nakama.append(b)

# main()
print(main())


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted