Last Substring In Lexicographical Order

Let create an empty string ‘lastSubstr’, and then one by find all the substring of ‘Str’ and compare them with ‘lastSubstr’, if the substring is lexicographically greater than ‘lastSubstr’, then updates ‘lastSubtr’ value to this substring. Note in most of the programming languages operator > or < can be used to compare string lexicographically.

Algorithm

• Create an empty string ‘lastSubstr’.
• Run a loop where ‘i’ ranges from 0 to N-1 and for each ‘i’ do the following
  • Create an empty string ‘curSubstr’.
  • Run a loop where ‘j’ ranges from ‘i’ to N - 1 and for each ‘j’ -:
    • Append the jth character of Str at the end of curSubstr’
    • If  curSubstr’  > ‘lastSubstr’, then do lastSubstr := curSubstr. 
• Return lastSubstr’.

We can prove that the lexicographically largest substring or last substring in lexicographical order will be one of the suffixes of the given string.   

We can prove it by contradiction, let assume that a substring Str[i...j]  is the last substring of string ‘Str’ of length ‘N’ in ’ lexicographical order. Here j < N-1, i.e Str[i..j] is not a suffix.   Then Str[i..j+1] > Str[i..j] because Str[i...j] is the prefix of Str[i...j+1],  That proves our assumption is wrong.

Algorithm

• Create two empty strings ‘lastSubstr’ and ‘curSuffix’.
• Run a loop where ‘i’ ranges from N - 1 to 0 (i.e in reverse order) and for each ‘i’ do the following
  • Add the ith character of Str at the start of the string ‘curSuffix’.
  • If  curSuffix’  > ‘lastSubstr’, then do lastSubstr := curSuffix. 
• Return lastSubstr’.

As discussed in the previous approach, the lexicographically largest substring or last substring in lexicographical order will be one of the suffixes of the given string.   

We can find this suffix more optimally by using two pointers ‘i’ and ‘j’. Initially, we keep ‘i’ at index 0, i.e ‘i’ := 0, and  ‘j’ at index 1, i.e ‘j’:=1. We also initialize an integer variable ‘k’:= 0.

Now we will move pointer ‘i’ and ‘j’ in such a way, that at any instant the optimal index (i.e index at which lexicographically largest suffix start)  will not be before ‘i’ or in between ‘i’ and ‘j’ (i &  j exclusive). To do this at each step we check whether the substring Str[i..k] is equal to, greater than, or smaller than substring Str[j..k]. If Str[i..k] is equal to Str[j..k] then we can’t say anything about the optimal index, so we increment ‘k’ by ‘1’ and explore the next characters in order to make a decision. If Str[i..k] > Str[j..k], then any index between ‘j’ to ‘k’ cannot be an optimal index, so we increment ‘j’ by ‘k+1’ and  update ‘k’: = 0. 

Or if Str[i..k] < Str[j..k] then ‘i’ cannot be an optimal index and also any index between ‘i’ & ‘j’ is not an optimal index, so we update ‘i’ with max(i+k+1, j), j = i+1 and k:= 0 Note, we can also skip already matched things. When j + k > |Str|, then ‘i’ will be the required optimal index.

Algorithm

• Initialize three integers ‘i’ := 0, ‘j’ := 1, and  ‘k’ : = 0.
• Run a loop till j + K < N and in each iteration do the following -:
  • If Str[i + k] = Str[j + k], then increment ‘k’  by ‘1’
  • If Str[i + k] > Str[j + k], then increment ‘j’ by ‘k + 1’ and do ‘k’ := 0.
  • If  Str[i + k] < Str[j + k], then update i = max(i + k + 1, j)’, ‘j’ = i + 1 and do ‘k’ := 0.
• Return suffix starts at index ‘i’.