Syed Munawwar Syed Munawwar - 5 months ago 33
Python Question

Find next highest lexicgraphic permutation of a string

given a string W, what i want to achieve its next string lexicographically greater.

eg 1:
givenstring = "hegf"
nexthighest = "hefg"

what i have tried till now is here,

from itertools import permutations
q = int(input())
for i in range(q):
s = input()
if s == s[::-1]:
print("no answer")
x = ["".join(p) for p in list(permutations(s))]
index = x.index(s)

since this is not the efficient way to solve this. can u please suggest me better way to solve this problem


here is best way to solve this problem

def NextHighestWord(string):
    S = [ord(i) for i in string]
    #find non-incresing suffix from last
    i = len(S) - 1
    while i > 0 and S[i-1] >= S[i]:
        i = i - 1
    if i <= 0:
        return False

    #next element to highest is pivot
    j = len(S) - 1
    while S[j] <= S[i -1]:
        j = j - 1
    S[i-1],S[j] = S[j],S[i-1]

    #reverse the suffix
    S[i:] = S[len(S) - 1 : i-1 : -1]
    ans = [chr(i) for i in S]
    ans = "".join(ans)
    return True

test = int(input())
for i in range(test):
    s = input()
    val = NextHighestWord(s)
    if val:
        print("no answer")