Syed Munawwar - 1 year ago 111
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 Source

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")
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download