LeetCode 1163. Last Substring in Lexicographical Order Solution in Java, C++, Python & More | Explanation + Code

Description

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 * 105
• s contains only lowercase English letters.

Solutions

Solution 1: Two pointers

We notice that if a substring starts from position i, then the largest substring with the largest dictionary order must be s[i,..n-1], which is the longest suffix starting from position i. Therefore, we only need to find the largest suffix substring.

We use two pointers i and j, where pointer i points to the starting position of the current largest substring with the largest dictionary order, and pointer j points to the starting position of the current substring being considered. In addition, we use a variable k to record the current position being compared. Initially, i = 0, j=1, k=0.

Each time, we compare s[i+k] and s[j+k]:

If s[i + k] = s[j + k], it means that s[i,..i+k] and s[j,..j+k] are the same, and we add k by 1 and continue to compare s[i+k] and s[j+k];

If s[i + k] \lt s[j + k], it means that the dictionary order of s[j,..j+k] is larger. At this time, we update i = i + k + 1, and reset k to 0. If i ≥ j at this time, we update pointer j to i + 1, that is, j = i + 1. Here we skip all suffix substrings with s[i,..,i+k] as the starting position, because their dictionary orders are smaller than the suffix substrings with s[j,..,j+k] as the starting position.

Similarly, if s[i + k] \gt s[j + k], it means that the dictionary order of s[i,..,i+k] is larger. At this time, we update j = j + k + 1 and reset k to 0. Here we skip all suffix substrings with s[j,..,j+k] as the starting position, because their dictionary orders are smaller than the suffix substrings with s[i,..,i+k] as the starting position.

Finally, we return the suffix substring starting from i, that is, s[i,..,n-1].

The time complexity is O(n), where n is the length of string s. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def lastSubstring(self, s: str) -> str: i, j, k = 0, 1, 0 while j + k < len(s): if s[i + k] == s[j + k]: k += 1 elif s[i + k] < s[j + k]: i += k + 1 k = 0 if i >= j: j = i + 1 else: j += k + 1 k = 0 return s[i:](code-box)

class Solution { public String lastSubstring(String s) { int n = s.length(); int i = 0; for (int j = 1, k = 0; j + k < n;) { int d = s.charAt(i + k) - s.charAt(j + k); if (d == 0) { ++k; } else if (d < 0) { i += k + 1; k = 0; if (i >= j) { j = i + 1; } } else { j += k + 1; k = 0; } } return s.substring(i); } }(code-box)

class Solution { public: string lastSubstring(string s) { int n = s.size(); int i = 0; for (int j = 1, k = 0; j + k < n;) { if (s[i + k] == s[j + k]) { ++k; } else if (s[i + k] < s[j + k]) { i += k + 1; k = 0; if (i >= j) { j = i + 1; } } else { j += k + 1; k = 0; } } return s.substr(i); } };(code-box)

func lastSubstring(s string) string { i, n := 0, len(s) for j, k := 1, 0; j+k < n; { if s[i+k] == s[j+k] { k++ } else if s[i+k] < s[j+k] { i += k + 1 k = 0 if i >= j { j = i + 1 } } else { j += k + 1 k = 0 } } return s[i:] }(code-box)

function lastSubstring(s: string): string { const n = s.length; let i = 0; for (let j = 1, k = 0; j + k < n; ) { if (s[i + k] === s[j + k]) { ++k; } else if (s[i + k] < s[j + k]) { i += k + 1; k = 0; if (i >= j) { j = i + 1; } } else { j += k + 1; k = 0; } } return s.slice(i); }(code-box)