In this article, we are going to find the lexicographic next string for the given string.

What is lexicographic next string?

Lexicographic next string for a given string is the string whose rank is just 1 more than that for the current string.
For e.g.:- If we have to find the lexicographic next string of ABC then it will be ACB as it will be the next in lexicographic order as the rank of ACB is 2 and that of ABC is 1.

Some approaches :-

One approach is to find all the permutations which can be made from the given string, store them in an array which will store all the possible strings from those set of characters in an ascending order, and then searching for the string of which we need to find lexicographic next string, and the picking the string just next to the searched string will give us lexicographic next string for that string.

Algorithm 1:-

1. Create an array of all possible permutations for the set of given characters. You can look into the link for this purpose: Permutations of String
2. Search for the given string in the array .
3. Store the index of the given string in that array in a variable.
4. Increase the index by 1, and retrieve the string of that index from the array.
5. Retrieved string will be the lexicographic next string.

Implementation:-

# permuted_array is our list to store the permutations in lexicographic order
global permuted_array 
permuted_array=[]
#count is our array to store the index for permutations of various length. 
global count
#function to calculate the permutations.
def permute(remaining):
    if len(remaining)==1:
        return remaining
    for i in range(0,len(remaining)):
    #We splice the strings to get substrings which further will be reduced.
        string=remaining[0:i]+remaining[i+1:len(remaining)]
    #Recurring the spliced string to generate shorter strings.
        permuted=permute(string)
    # Base case.
        if(len(permuted)==1):
    # Concatenate the strings 
            permuted_array.append(remaining[i]+permuted)
        else:
            j=len(permuted_array[-1])#To find the length of the shortest length string in the permuted_array at any given time as modifications will be done to only those strings.
            for k in permuted_array:
                if(len(k)!=j):
                    continue
                else:
     #Concatenating the required substrings.
                    permuted_array[count[len(remaining)-1]]=remaining[i]+permuted_array[count[len(remaining)-1]]
                count[len(remaining)-1]+=1
    return permuted_array
test_string=input("Enter the string")
#sorting the input string, as only then we will be able to find out the lexicographic order using this algp, otherwise it will just print permutations irrespectove of lexicographic order.
string = ''.join(sorted(test_string))
count=[len(string)]
for i in range(0,len(string)):
    count.append(0)
permute(string)
print(permuted_array)
if test_string in permuted_array:
    index=permuted_array.index(test_string)
    if(index==len(permuted_array)-1):
        print("No greater string possible with this set of characters, in the given order")
    else:
        print(permuted_array[index+1])

Complexity:-

Its time complexity is O(n * n!) , as we are using recursive method to create an array which itself is of the order of O(n * n!), and thus, we arrive at the concluded time complexity.
Space complexity is O(n!) as we require an array to store the permutations and the number of permutations equals n! and thus, the given space complexity.

Algorithm 2:-

Now, we will see a much more feasible algorithm to find lexicographic next string.

1. To find the lexicographic next string simply find the rightmost i, for which string[i]<string[i+1], if you don't get one then it means you can't get lexicographic next string, as it is the last string in the lexicographic order which can be made from those characters.
2. Once you have found the i, find the ceiling of string[i] in the portion of the list from index i+1 to the end of the string.
3. Swap those two .
4. Sort the resultant string from position i+1 to the end of the string in ascending order.
5. Newer string will be the lexicographic next string.

For e.g.:-

If we have to find the lexicographic next string for the string "Genus", then here, the rightmost "i" for which string[i]<string[i+1] will be 2(assuming that our indexing begins from 0), as "n"<"u".
Now, we need to find the ceiling of "n" in the portion off the string to the right of "n", it will be "s".
Now, swap "n" and "s" and hence, our string becomes "Gesun".
Now, we need to sort the portion of the string to the right of index 2 in ascending order, thus, our string becomes "Gesnu", which will be the desired lexicographic next string.

Implementation :-

p=input("Enter the string:")
a=len(p)
i=0
#Position variable captures the position i for which string[i]<string[i+1]
position=0
while(i<a-1):
    if(p[i]<p[i+1]):
        position=i
    i+=1
j=position+1
#min is used to find the ceiling of string[i]
min=100
#swap_position stores the position of ceiling of string[i]
global swap_position
swap_position=0
#Finding swap_position
while(j<a):
    if(ord(p[j])-ord(p[position])<min and (ord(p[j])-ord(p[position]))!=0):
        min=ord(p[j])-ord(p[position])
        swap_position=j
    j+=1
#new array stores the array after exchanging string[i] with its ceiling.
new=[]
count=0
#swapping string[position] with string[swap_position]
while(count<a):
    if(count==position):
        new.append(p[swap_position])
    elif(count==swap_position):
        new.append(p[position])
    else:
        new.append(p[count])
    count+=1

#Sorting the portion of the array from i+1 to end of the list in new
new[position+1:a]=sorted(new[position+1:a])
q=0
#m stores the lexicographic next string
m=''
while(q<a):
   m+=new[q]
   q+=1
print("Lexicographic next string is: ",m)

Complexity:-

Time complexity for the above algorithm is O(n) , while the space complexity is of the O(n), as we have used another array to perform the operations for lexicographically next string.