Given a string s, return the last substring of s in lexicographical order.
Example 1:
Input: s = "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".
Example 2:
Input: s = "leetcode"
Output: "tcode"
Constraints:
1 <= s.length <= 4 * 105s contains only lowercase English letters.Last Substring in Lexicographical Order - LeetCode
// We use "j" to find a better starting index. If any is found, we use it to update "i"
// 1."i" is the starting index of the first substring
// 2."j" is the staring index of the second substring
// 3."k" is related to substring.length() (eg. "k" is substring.length()-1)
// Case 1 (s[i+k]==s[j+k]):
// -> If s.substr(i,k+1)==s.substr(j,k+1), we keep increasing k.
// Case 2 (s[i+k]<s[j+k]):
// -> If the second substring is larger, we update i with max(i+k+1,j).
//Since we can skip already matched things (The final answer is s.substr(i))
// Case 3 (s[i+k]>s[j+k]):
// -> If the second substring is smaller, we just change the starting index of the second string to j+k+1.
//Because s[j]~s[j+k] must be less than s[i], otherwise "i" will be updated by "j". So the next possible candidate is "j+k+1".
class Solution {
public:
string lastSubstring(string s) {
int n = s.size();
int i = 0;// starting point of 1st substring
int j = 1;// starting point of second substring
int k = 0; // offset
while(j+k<n)
{
if(s[i+k]==s[j+k])
k++;
else if(s[i+k]<s[j+k])
{
i = i+k+1;
j = i+1;
k = 0;
}
else
{
j = j+k+1;
k = 0;
}
}
return s.substr(i);
}
};