Syed Munawwar - 17 days ago 7

Python Question

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")
```

Source (Stackoverflow)

Comments