Syed Munawwar Syed Munawwar - 17 days ago 7
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")
else:
x = ["".join(p) for p in list(permutations(s))]
x.sort()
index = x.index(s)
print(x[index+1])


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

Answer

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)
    print(ans)
    return True

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