# Last Substring In Lexicographical Order

#### You are given a string ‘Str’ of length ‘N’. Find the last substring of ‘Str’ in lexicographical order.

#### In Lexicographical order string ‘S1’ comes before string ‘S2’ if S1 is the prefix of S2 and (|S1| < |S2|), or if none of them is a prefix of the other and at the first position where they differ, the character in ‘S1’ is smaller than the character in ‘S2’.

##### Example :

```
Consider string ‘Str’ = “abba”, then its substring in lexicographical order is [“a”, “ab”, “abb”, “abba”, “b”, “bb”, “bba”]. Clearly, the last substring in lexicographical order is “bba”.
```

##### Input format :

```
The first line of input contains an integer ‘T’ denoting the number of test cases, then ‘T’ test cases follow.
The first and only line of each test case consists string ‘Str’
```

##### Output format :

```
For each test case, in a separate line print the last substring of ‘Str’ in lexicographical order.
```

#### Note :

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 50
1 <= N <= 10^4
‘Str’ contains only lowercase English letters.
Time limit: 1 sec
```

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.**

- Append the jth character of

**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’.**