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):
S = input()
Z = sorted(list(S))
G = ["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"]
ans = []
for s in S:
    if s not in ans:
        ans.append(s)
    else:
        i = G.index(s)
        j = 0
        while j < 27:
            if G[(i + j) % 26] not in ans:
                ans.append(G[(i + j) % 26])
                break
            j += 1

for i in range(len(ans)):
    if "".join(ans[:i+1]) > S:
        print("".join(ans[:i+1]))
        exit()
for i in range(100):
    aaa = sorted(ans)
    print(ans)
    if "".join(ans) > S:
        print("".join(ans))
        exit()
    else:
        i = G.index(aaa[0])
        j = 0
        while j < 27:
            if G[(i + j) % 26] not in ans:
                ans.append(G[(i + j) % 26])
                break
            j += 1

ans = "".join(ans)
S = "".join(S)
if ans == S:
    ans = list(ans)
    aaa = sorted(list(ans))
    i = G.index(aaa[0])
    j = 0
    while j < 27:
        if G[(i + j) % 26] not in ans:
            ans.append(G[(i + j) % 26])
            break
        j += 1
    else:
        for i in range(len(S)-1, -1, -1):
            for j in range(i, -1, -1):
                if S[i] > S[j]:
                    print(S[:j] + S[i])
                    exit()
ans = "".join(ans)
if ans > S:
    print(ans)
else:
    print(-1)






S = input()
C = [chr(97+i) for i in range(26)]

if len(S) != 26:
    for c in C:
        if c not in S:
            print(S + c)
            break
else:
    K = []
    for i in range(25, -1, -1):
        K.append(S[i])
        K.sort()
        for j in range(25, -1, -1):
            if K[0] > S[j]:
                print(S[:j] + K[0])
                exit()
print(-1)



S = input()
C = [chr(97+i) for i in range(26)]


if S == "".join(C.sort(reverse=True)):
    print(-1)

elif len(S) != 26:
    for c in C:
        if c not in S:
            print(S + c)
            break
else:
    K = []
    for i in range(25, -1, -1):
        K.append(S[i])
        K.sort()
        for j in range(25, -1, -1):
            if K[0] > S[j]:
                print(S[:j])
                exit()



S = input()
A = [chr(ord("a")+i) for i in range(26)]

if len(set(S)) < 26:
    for a in A:
        if a not in S:
            print(S+a)
            break
else:
    X = []
    for i in range(25, 0, -1):
        if S[i] > S[i-1]:
            X.append(S[i])
            X = sorted(list(filter(lambda x: x > S[i-1], X)))
            print(S[:i-1]+X[0])
            break
        else:
            X.append(S[i])
    else:
        print(-1)

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Accepted