1163. Last Substring in Lexicographical Order
Given a string s, returnthe 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 . l e n g t h < = 4 ∗ 10 5 1 <= s.length <= 4 * 10^51<=s.length<=4∗105
- s contains only lowercase English letters.
From: LeetCode
Link: 1163. Last Substring in Lexicographical Order
Solution:
Ideas:
Maintain two candidate starting positions i and j, compare their suffixes character by character, and discard the lexicographically smaller candidate each time so every position is processed at most once in O(n) time.
Code:
char*lastSubstring(char*s){intn=strlen(s);inti=0,j=1,k=0;while(j<n){k=0;while(j+k<n&&s[i+k]==s[j+k]){k++;}if(j+k==n){break;}if(s[i+k]<s[j+k]){i=i+k+1;if(i>=j){j=i+1;}}else{j=j+k+1;}}returns+i;}
