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()

if S == "".join([chr(i) for i in reversed(range(97, 97 + 26))]):
    print(-1)
    exit()

M = 96
for i in range(97, 97 + 26):
    if not chr(i) in S:
        M = i
        break
if M != 96:
    print(S + chr(M))
    exit()

unused = [False] * 128
for i in reversed(range(len(S))):
    for j in range(ord(S[i]) + 1, 97 + 26):
        if unused[j]:
            print(S[0:i] + chr(j))
            exit()
    unused[ord(S[i])] = True

Submission status: Accepted

Solution code:
S=input()
if S=='zyxwvutsrqponmlkjihgfedcba':
  print(-1)
  exit()
alp='abcdefghijklmnopqrstuvwxyz'
N=len(S)
if N<26:
  T=S+alp
  i=0
  while T.index(alp[i])<N:
    i+=1
  print(S+alp[i])
  exit()
  
i=-1
nums=[alp.index(S[i])]
while max(nums)==nums[-1]:
  i-=1
  nums.append(alp.index(S[i]))

out=S[:-len(nums)]
tmp=26
for i in nums[:-1]:
  if i>nums[-1] and tmp>i:
    tmp=i
    
print(out+alp[tmp])

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    from string import ascii_lowercase

    S = input()

    ctr = Counter(S)
    for count in ctr.values():
        if count > 1:
            print(-1)
            return

    for char in ascii_lowercase:
        if ctr[char] == 0:
            print(S + char)
            return

    lis = list(S)
    stock = []
    ma = None
    while lis:
        x = lis.pop()
        if ma is None or ma < x:
            ma = x
        stock.append(x)
        if lis and lis[-1] < ma:
            stock.sort()
            for char in stock:
                if lis[-1] < char:
                    print(''.join(lis[:-1]) + char)
                    return
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
alphabet = ['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 i in alphabet:
    if i not in S:
        print(S + i)
        break
else:
    output = False
    while len(S) > 0 and not output:
        last = alphabet.index(S[-1])
        for i in alphabet[last + 1:]:
            if i not in S[:-1]:
                print(S[:-1] + i)
                output = not(output)
                break
        else:
            S = S[:-1]
    if not output:
        print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    # sys.stdin = open("sample.txt")
    S = Scanner.string()
    if len(S) == 26:
        if list(S) == list(reversed(list(string.ascii_lowercase))):
            print(-1)
            return
        i = 0
        for i in reversed(range(25)):
            if S[i] < S[i+1]:
                break
        ans = S[:i]
        k = S[i]
        for s in sorted(S[i+1:]):
            if k < s:
                ans += s
                break
        print(ans)
        return
    else:
        T = Counter(S)
        for c in string.ascii_lowercase:
            if T[c] == 0:
                print(S + c)
                return
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import string
S = input()
if len(S) == 26:
    if S == "zyxwvutsrqponmlkjihgfedcba":
        print(-1)
    else:
        i = len(S) - 1
        while 0 <= i:
            if S[i-1] < S[i]:
                break
            i -= 1
        ans = ""
        for x in range(i):
            ans += S[x]

        for j in S[i:][::-1]:
            if ans[-1] < j:
                ans = ans[:-1] + j
                break

        print(ans)

    exit()

chars_set = set(S)
for c in string.ascii_lowercase:
    if c not in chars_set:
        S += c
        break
print(S)

Submission status: Accepted

Solution code:
S = list(input())

if len(S) < 26:
    W = list('abcdefghijklmnopqrstuvwxyz')
    for s in S:
        W.remove(s)
    S += W[0]
    print(*S, sep='')
else:
    s_last = S[-1]
    idx = -1
    for i in range(24, -1, -1):
        s = S[i]
        if s > s_last:
            s_last = s
        else:
            idx = i
            break
    if idx == -1:
        print(-1)
    else:
        res = []
        for s in S[idx+1:]:
            if s > S[idx]:
                res.append(s)
        res.sort()
        print(*(S[:idx] + [res[0]]), sep='')

Submission status: Accepted

Solution code:

#coding:utf-8
S = input()
if len(S)<26:
    for i in [chr(i) for i in range(97, 97+26)]:
        if not i in S:
            print (S+i)
            exit()
else:
    
    for i in range(len(S)-1):


        if (S[-i-1] > S[-i-2]):
            for j in S[-i-1:][::-1]:
                #print (j)
                if (S[-i-2]<j):
                    print (S[:-i-2]+j)
                    exit()
        else:
            pass
print (-1)

Submission status: Accepted

Solution code:
import sys

s = input()
if s == "zyxwvutsrqponmlkjihgfedcba":
	print(-1)
	sys.exit()
if len(s) < 26:
	flg = [0] * 26
	for i in range(len(s)):
		flg[ord(s[i])-97] = 1
	ans = s + chr(flg.index(0)+97)
	print(ans)

else:
	candidate = []
	for i in range(25,0,-1):
		candidate.append(s[i])
		if s[i-1] < s[i]:
			obj = s[i-1]
			ind = i-1
			break

	candidate.append(obj)
	candidate.sort()
	switch = candidate[candidate.index(obj)+1]
	ans = s[:ind] + switch
	print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
s=input()
n=len(s)
ls=[0]*26
if s == "zyxwvutsrqponmlkjihgfedcba":
  print(-1)
  exit()
if n<26:
  for i in range(n):
    ls[ord(s[i])-97]=i+1
  for i in range(26):
    if ls[i]==0:
      x=i
      break
  print(s+chr(x+97))
else:
  for i in range(n):
    ls[i] = ord(s[i])-97
  if ls[25]>ls[24]:
    print(s[:24]+s[25])
  else:
    tmp = []
    for i in range(24,-1,-1):
      tmp.append(ls[i+1])
      if ls[i+1]>ls[i]:
        tmps = sorted(tmp)
        x = bisect(tmps,ls[i])
        print(s[:i]+chr(tmps[x]+97))
        break

Submission status: Accepted

Solution code:
S = input()
if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()
S = [ord(a)-97 for a in S]
if len(S) < 26:
    for i in range(26):
        if i not in S:
            T = S + [i]
            print("".join([chr(a+97) for a in T]))
            exit()
else:
    for i in range(26)[::-1]:
        for j in range(S[i]+1, 26):
            if j in S[i:]:
                T = S[:i] + [j]
                print("".join([chr(a+97) for a in T]))
                exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import bisect
import collections
import itertools
import heapq
import string
import sys
sys.setrecursionlimit(10**9)
def gcd(a,b):return math.gcd #最大公約数
def lcm(a,b):return (a*b) // math.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def 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 is_prime(n):
    if n == 1: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False 
    return True
def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n + 1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def sieve_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime
s = input()
S = list(s)
a = string.ascii_lowercase
od = collections.OrderedDict()
for i in range(len(a)):
    od[a[i]] = 0
for st in S:
    od[st] = 1
for k, v in od.items():
    if v == 0:
        print(join(S)+k)
        exit()

prev = S.pop()
od[prev] = 0
done = False
for i in range(len(S)):
    prev = S.pop()
    od[prev] = 0
    target = False 
    for k,v in od.items():
        if prev == k:
            target = True
            continue
        if target == True and v == 0:
            print(join(S)+k)
            done = True
            break
    if done == True:
        break
if done == False:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    s = S()
    if "".join(s) == "zyxwvutsrqponmlkjihgfedcba":
        print(-1)
        return
    l = [chr(ord("a") + i) for i in range(26)]
    for si in s:
        l.remove(si)
    if l == []:
        s = s[::-1]
        l.append(s[0])
        ans = []
        f = True
        for si in s[1:]:
            if f:
                if l[-1] > si:
                    f = False
                    x = si
                else:
                    l.append(si)
            else:
                ans.append(si)
        l.sort()
        for ai in l:
            if ai > x:
                print("".join(ans[::-1]) + ai)
                return
    else:
        print("".join(s) + l[0])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from string import ascii_lowercase as alp
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	S = input().rstrip()

	# 使われていない文字が残っている場合
	for i, letter in enumerate(alp):
		if not S.count(letter):
			print(S+letter)
			sys.exit()

	# 26文字全て使われている場合
	# 後ろから見ていって、昇順に並んでいる箇所の2文字目を
	# より後ろの文字に入れ替える
	# ABCDE(01234) -> ABCED(01243) にするイメージ
	tmp = []
	for i in range(len(S)-1, 0, -1):
		if S[i] < S[i-1]:
			tmp.append(S[i])
		elif S[i] > S[i-1]:
			tmp.append(S[i])
			tmp.sort()
			# print(tmp, S[i-1])
			for t in tmp:
				if S[i-1] < t:
					print(S[:i-1]+t)
					sys.exit()
	
	# 全て降順に並んでいる場合(EDCBA)はこれ以上変えようがないので-1
	print(-1)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
from string import ascii_lowercase as alp
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	S = input().rstrip()
	# zyxwvutsrqponmlkjihgfedcba の例
	if S == alp[::-1]:
		print(-1)
		sys.exit()
	# 使われていない文字が残っている場合
	for i, letter in enumerate(alp):
		if not S.count(letter):
			print(S+letter)
			sys.exit()
	# 26文字全て使われている場合
	# => ABCDE(01234) -> ABCE(0124) にする
	tmp = []
	for i in range(len(S)-1, 0, -1):
		if S[i] < S[i-1]:
			tmp.append(S[i])
		elif S[i] > S[i-1]:
			tmp.append(S[i])
			tmp.sort()
			# print(tmp, S[i-1])
			for t in tmp:
				if S[i-1]<t:
					print(S[:i-1]+t)
					sys.exit()

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
S = input().strip()
C = {chr(i):0 for i in range(97,123)}
n = len(S)
for a in S:
    C[a] += 1
flag = 0
for i in range(97,123):
    if C[chr(i)]==0:
        x = S+chr(i)
        flag = 1
        break
if flag==0:
    cnt = -2
    while cnt>=-n:
        b = S[cnt]
        A = []
        for i in range(n+cnt+1,n):
            if ord(b)<ord(S[i]):
                A.append(S[i])
        if len(A)>0:
            A = sorted(A)
            x = S[:cnt]+A[0]
            flag = 1
            break
        cnt -= 1
if flag == 1:
    print(x)
else:
    print(-1)

Submission status: Accepted

Solution code:
from string import ascii_lowercase
from sys import stdin, exit
S = stdin.readline().rstrip()
set_s = set(S)

if len(S) < 26:
  for c in ascii_lowercase:
    ans = S+c
    if set_s != set(ans) and S < ans:
      print(ans)
      exit()
else:
  for i in range(len(S)-1, -1, -1):
    for c in ascii_lowercase:
      if S[i] < c and c not in S[:i]:
        print(S[:i]+c)
        exit()
print(-1)

Submission status: Accepted

Solution code:
s = input()
included = set()
for i in s:
    included.add(i)
for i in range(ord('a'), ord('z') + 1):
    if not chr(i) in included:
        print(s + chr(i))
        exit()
ans = ''
for i in range(len(s) - 1, -1, -1):
    for j in range(ord(s[i]), ord('z') + 1):
        now = s[:i] + chr(j)
        if not chr(j) in s[:i] and s[:i + 1] != now:
            print(now)
            exit()
print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = read().rstrip().decode('utf-8')

alphabet = set(chr(ord('a')+x) for x in range(26))

def F_short(S):
    se = alphabet - set(S)
    x = min(se)
    return S + x

def F_long(S):
    if S == ''.join(sorted(alphabet, reverse=True)):
        return '-1'
    # 1文字ずつpopして、増加チャンスを待つ
    cand = []
    S = list(S)
    while True:
        x = S[-1]
        if not cand or (x > max(cand)):
            cand.append(S.pop())
            continue
        y = min(ch for ch in cand if ch > x)
        return ''.join(S[:-1]) + y

L = len(S)
answer = F_short(S) if L < 26 else F_long(S)
print(answer)

Submission status: Accepted

Solution code:
al = "abcdefghijklmnopqrstuvwxyz"
s = input()
if len(s)<26:
  for i in al:
    if i not in s:
      print(s+i)
      break
else:
  if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
  else:
    k = []
    for i in range(25, 0, -1):
      k.append(s[i])
      if s[i-1] < s[i]:
        for j in sorted(k):
          if j > s[i-1]:
            print(s[:i-1] + j)
            exit()

Submission status: Accepted

Solution code:
import string

S = input()
if len(S) < 26:
  for a in string.ascii_lowercase:
    if a not in S:
      print(S+a)
      exit()
else:
  S = list(S)
  L = [S[len(S)-1]]
  for i in range(24,-1,-1):
    for a in sorted(L):
      if a > S[i]:
        if i > 0:
          print(''.join(S[:i])+a)
        else:
          print(a)
        exit()
    L.append(S[i])
  print(-1)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
alp = 'abcdefghijklmnopqrstuvwxyz'
if N<25:
  for a in alp:
    if a not in S:
      print(S+a)
      exit()
else:
  for i in range(N-1,-1,-1):
    nextS = ''
    for s in S[i:]:
      tmpS = S[:i] + s
      if tmpS == S:continue
      
      if nextS == '':
        if sorted([S,tmpS])[1] == tmpS:
          nextS = tmpS
      elif sorted([S,tmpS])[1] == tmpS and sorted([tmpS,nextS])[0] == tmpS:
        nextS = tmpS
     
    if nextS != '':
      print(nextS)
      exit()
  print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
S = input()

can_use = [True for n in range(ord('a'), ord('z') + 1)]
for s in S:
    i = ord(s) - ord('a')
    can_use[i] = False

if any(can_use):
    for n, use in enumerate(can_use):
        if use:
            S += chr(ord('a') + n)
            print(S)
            exit()
else:
    # 全て使われている
    for i in range(len(S)-1, 0, -1):
        if ord(S[i-1]) < ord(S[i]):
            c = sorted([c for c in S[i-1:] if c > S[i-1]])[0]
            ans = S[:i-1] + c
            print(ans)
            exit()

    print(-1)

Submission status: Accepted

Solution code:
s = input()
len_s = len(s)
x = "abcdefghijklmnopqrstuvwxyz"
ls = {i : j for j, i in enumerate(x)}
if len_s < 26:
    set_s = set(s)
    candidate = list(set(x).difference(set_s))
    candidate.sort()
    print(s + candidate[0])
else:
    if s == x[::-1]:
        print(-1)
    else:
        res = ""
        inv_s = s[::-1]
        _max = -1
        for i, j in enumerate(inv_s):
            if _max > ls[j]:
                break
            _max = max(_max, ls[j])
        res = s[:-1-i]
        candidate = [k for k in inv_s[:i] if k > j]
        print(res + candidate[0])

Submission status: Accepted

Solution code:
S = input()
# 接尾辞の降順が崩れるタイミングが狙い目
if len(S) == 26:
    # 降順が崩れるタイミングを狙う
    pointa = -1
    for i in reversed(range(1, 26)):
        if ord(S[i]) > ord(S[i-1]):  # 後ろから見て降順が崩れたタイミング
            pointa = i-1
            break
    # 後ろからi-1文字目を書き換えればok
    if pointa != -1:
        happend = list(S[:pointa])  # ここに出ていないかつ, S[pointa]より大きい最小のもの
        for i in range(26):
            if chr(ord("a") + i) not in happend and ord("a")+i > ord(S[pointa]):
                target = chr(ord("a") + i)
                break
        print(S[:pointa]+target)
    else:
        print(-1)

else:
    # 1文字付け足すだけ
    happend = list(S)
    for i in range(26):
        if chr(ord("a") + i) not in happend:
            target = chr(ord("a") + i)
            break
    print(S+target)

Submission status: Accepted

Solution code:
import sys

S = list(input())
    
for i in range(len(S)):
    S[i] = ord(S[i]) - ord("a")

if len(S) == 26:
    t = 26
    for i in range(len(S)-1)[::-1]:
        for j in range(i+1,26):
            if S[i] < S[j] and t > S[j]:
                t = S[j]
        if t != 26:
            S = S[:i] + [t]
            for k in range(len(S)):
                S[k] = chr(S[k] + ord("a"))
            print("".join(S))
            sys.exit()
    print(-1)

else:
    n = set(range(26)) - set(S)
    S.append(min(n))
    for i in range(len(S)):
        S[i] = chr(S[i] + ord("a"))
    print("".join(S))

Submission status: Accepted

Solution code:
S = input()
if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()
if len(S) == 26:
    now = S[-1]
    for i in reversed(range(26)):
        if ord(now) > ord(S[i]):  # 辞書順が崩れた瞬間
            happened = list(S[:i+1])
            for j in range(26):
                if chr(ord("a") + j) not in happened and ord("a") + j > ord(S[i]):
                    print(S[:i]+chr(ord("a") + j))
                    exit()
        else:
            now = S[i]

else:
    happened = list(S)
    for i in range(26):
        if chr(ord("a") + i) not in happened:
            print(S+chr(ord("a") + i))
            exit()

Submission status: Accepted

Solution code:
import sys
import bisect

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

a2z = set(list(map(chr, range(97, 123))))
S = rs()
if len(S) < 26:
    unused = a2z - set(S)
    print(S + sorted(list(unused))[0])
    exit()
else:
    l = [S[25]]
    for i in range(24, -1, -1):
        j = bisect.bisect_left(l, S[i])
        if j != len(l):
            answer = S[:i] + l[j]
            print(answer)
            exit()
        else:
            l.append(S[i])
            l.sort()
print(-1)
#47

Submission status: Accepted

Solution code:
s = list(input())

n = len(s)
a = "abcdefghijklmnopqrstuvwxyz"
ans = -1
if n < 26:
    for v in a:
        if v not in s:
            ans = "".join(s + [v])
            break
else:
    for i in range(1, n)[::-1]:
        if s[i-1] < s[i]:
            j = a.index(s[i-1])
            for v in a[j:]:
                if v not in s[:i]:
                    s[i-1] =  v
                    ans = "".join(s[:i])
                    break
            break

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import string

s = stdin.readline().rstrip()
l = []
for i in string.ascii_lowercase:
    l.append(i)

for i in s:
    l.remove(i)

if s == string.ascii_lowercase[::-1]:
    print(-1)
    exit()
elif len(l) > 0:
    print(s+l[0])
else:
    k = s[::-1]
    li = [k[0]]
    for i in range(1,len(k)):
        li.append(k[i])
        if string.ascii_lowercase.index(k[i]) < string.ascii_lowercase.index(k[i-1]):
            a = li[-1]
            li.sort()
            print(s[:len(s)-i-1]+li[li.index(a)+1])
            exit()

Submission status: Accepted

Solution code:
import string
A = [chr(i) for i in range(ord('a'), ord('z')+1)]
B = {}
for i in range(26):
    B[A[i]] = i
s = input()
n = len(s)
def a():
    C = [0] * 26
    for i in range(n):
        C[B[s[i]]] = 1

    if n < 26:
        i = 0
        while C[i] == 1:
            i += 1
        return s + A[i]
    else:
        for i in range(25, -1, -1):
            t = s[i]
            for j in range(B[s[i]]+1, 26):
                if C[j] == 0:
                    return s[:i] + A[j]
            C[B[t]] = 0
        return -1
print(a())

Submission status: Accepted

Solution code:
S = input()
L = [i for i in range(97,123)]
n = len(S)
for i in range(n):
    L.remove(ord(S[i]))
if n <= 25:
    X = L[0]
    ans = S + chr(X)
else:
    T = []
    x = S[-1]
    T.append(x)
    for i in range(2,27):
        y = S[-i]
        if y > x:
            x = y
            T.append(y)
        else:
            break
    m = 26 - len(T)
    if m > 1:
        ans = S[0]
        for i in range(1,m-1):
            ans += S[i]
        for t in T:
            if t > S[m-1]:
                ans += t
                break
    elif m == 0:
        ans = -1
    else:
        for t in T:
            if t > S[m-1]:
                ans = t
                break
print(ans)

Submission status: Accepted

Solution code:
s = input()
a = [chr(i) for i in range(97, 97 + 26)]

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

if len(s) != 26:
    print(s + sorted(list(set(a) - set(s)))[0])
else:
    t = s
    s = list(s)
    n = len(s)
    for i in range(n - 1)[::-1]:
        if s[i] < s[i + 1]:
            break
    for j in range(n)[::-1]:
        if s[i] < s[j]:
            s[i], s[j] = s[j], s[i]
            break
    s = s[:i + 1] + s[i + 1:][::-1]

    ans = ""
    for i, j in zip(s, t):
        ans += i
        if i != j:
            print(ans)
            exit()

Submission status: Accepted

Solution code:
s = input()
a = [chr(i) for i in range(97, 97 + 26)]

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

if len(s) != 26:
    print(s + sorted(list(set(a) - set(s)))[0])
else:
    t = s
    s = list(s)
    n = len(s)
    for i in range(n - 1):
        if s[i] < s[i + 1]:
            j = i
    for i, v in enumerate(s[::-1]):
        if s[j] < v:
            s[j], s[n-i-1] = s[n-i-1], s[j]
            break
    s = s[:j + 1] + s[j + 1:][::-1]

    ans = ""
    for i, j in zip(s, t):
        ans += i
        if i != j:
            print(ans)
            exit()

Submission status: Accepted

Solution code:
s = input()
a = [chr(i) for i in range(97, 97 + 26)]

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

if len(s) != 26:
    print(s + sorted(list(set(a) - set(s)))[0])
else:
    j = 0
    for i in range(len(s) - 1):
        if s[i] < s[i + 1]:
            j = i
    x = []
    for i in s[j + 1:]:
        if s[j] < i:
            x.append(i)
    print(s[:j] + min(x))

Submission status: Accepted

Solution code:
from string import ascii_lowercase
D = {k:i for i, k in enumerate(ascii_lowercase)}

S = input()
n = len(S)

if n != 26:
    ans = S
    for c in ascii_lowercase:
        if c not in S:
            ans += c
            break
else:
    nokori = [D[S[-1]]]
    for i in range(24, -1, -1):
        res = 30
        for n in nokori:
            if D[S[i]] < n:
                res = min(res, n)
        if res == 30:
            nokori.append(D[S[i]])
        else:
            ans = S[:i] + ascii_lowercase[res]
            break
    else:
        ans = -1

print(ans)

Submission status: Accepted

Solution code:
S = [ord(i) for i in input()] + [96]

def solve() :
  for i in range(len(S) - 1, -1, -1) :
    for j in range(S[i] + 1, 97 + 26) :
      if not j in S[:i+1] :
        S[i] = j
        return ''.join(map(chr, S[:i+1]))
  return -1

print(solve())

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)
al=[chr(ord('a') + i) for i in range(26)]
#print(al)

if N < 26:
  for i in range(26):
    if al[i] not in S:
      S.append(al[i])
      print(*S,sep="")
      exit()
else:
  flg = False
  S = S[::-1]
  x = 0
  while x < len(S):
    id = al.index(S[x])
    if id == 25:
      S = S[x+1:]
    else:
      id += 1
      for k in range(id,26):
        if al[k] not in S:
          S[x] = al[k]
          S = S[::-1]
          print(*S,sep="")
          exit()
      S = S[x+1:]
  print(-1)

Submission status: Accepted

Solution code:
s=input()
ans=""

slist=list(s)
if(len(slist)==26):
    if(s=='zyxwvutsrqponmlkjihgfedcba'):
        print(-1)
    else:
        tlist=list(s)
        while(''.join(tlist)!='zyxwvutsrqponmlkjihgfedcba'):
            ttail=tlist.pop(-1)
            while(ttail=='z'):
                ttail=tlist.pop(-1)
            tlist.append(chr(ord(ttail)+1))

            if(len(tlist) == len(list(set(tlist)))):
                break

        print(''.join(tlist))
else:
    tlist=list(s)
    tlist.append('a')
    c=97
    while(ord('z') >= c):
        tlist[-1]=chr(c)
        if(len(list(set(slist))) != len(list(set(tlist)))):
            break
        else:
            c+=1
    print(''.join(tlist))

Submission status: Accepted

Solution code:
S=input()
for i in range(ord('a'),ord('z')+1):
  if chr(i) not in S:
    print(S+chr(i))
    break
else:
  for i in range(len(S)-1,-1,-1):
    for j in range(ord('a'),ord('z')+1):
      if j>ord(S[i]) and chr(j) not in S[:i]:
        print(S[:i]+chr(j))
        exit(0)
  else:
    print(-1)

Submission status: Accepted

Solution code:
S = input()

for i in range(ord('a'), ord('z')+1):
    if chr(i) not in S:
        print(S + chr(i))
        exit()
else:
    for i in range(len(S)-1, -1, -1):
        for j in range(ord('a'), ord('z')+1):
            if S[i] < chr(j) and chr(j) not in S[:i]:
                print(S[:i] + chr(j))
                exit()
    else:
        print(-1)

Submission status: Accepted

Solution code:
s = input()
alp = "abcdefghijklmnopqrstuvwxyz"

if len(s) < 26:
    for i in alp:
        if not i in s:
            ans = s + i
            break

else:
    tmp = []
    ss = list(s)
    for i in range(len(ss)):
        if i == 0:
            tmp.append(ss.pop())
            continue

        if alp.index(ss[-1]) > alp.index(tmp[-1]):
            tmp.append(ss.pop())
            continue
        else:
            remove = ss.pop()
            tmp.sort()
            for j in tmp:
                if j > remove:
                    renew = j
                    break
            ans = "".join(ss) + renew
            break
    else:
        ans = -1

print(ans)