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

here is another 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")