Leetcode: Last Substring in Lexicographical Order
This question is a relatively simple problem, and we want to return the last substring in lexicographical order. Given a string s, return the last substring of s in lexicographical order.
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 * 10^5
s contains only lowercase English letters.
We want to find the substring that would go the latest in the dictionary.
We should introduce a variable called offset, which is how many strings we have in the process from the starting point of all the candidates to the end.
Let's say we have an extreme case like babababababababababa... many ba's all repeating. In the beginning, we have all the candidates pointing. We should continuously make offsets different things like
b a b a b a b a b a b
ba ba ba ba ba
bab aba bab aba bab aba....
This method is inefficient since it would take O(n^2).
Here's the final class:
class Solution:
def lastSubstring(self, s: str) -> str:
n = len(s)
mmax = max(s)
candidates = [I for I, c in enumerate(s) if c == mmax]
offset = 1
while len(candidates) > 1:
curMax = max(s[i + offset] for I in candidates if I + offset < n)
newCand = []
for I, st in enumerate(candidates):
if I > 0 and candidates[i - 1] + offset == st:
continue
if st + offset < n and s[st + offset] == curMax:
newCand.append(st)
candidates = newCand
offset += 1
return s[candidates[0]:]
Nate17 has a really good explanation of how to write the code. According to him, we want to eliminate the candidates we are certain are not the solution, at last, the only one left our solution.
Give i < j , assuming for p < j and p != i, s[p:] is smaller than the maximum substring. So we eliminate that at first because now the first characters are greater for the j than the p, so we eliminate all p characters.
Now onto the next case.
for j = i + d if d >= 1 and k >= 0, if s[i + x] == s[j + x] and considering 0 <= x < k, we have several cases to discuss.
we increment k if s[i + k] == s[j + k], since this is obviously not the last string.
Now let's say s[i + k] > s[j + k]. We have a substring s[j + p0:] < s[i + p0:] = s[j - d + p0] = s[j + p1] < s[i + p1] and so on, where we have p0 = p1 + d > p1 > p2 ... until j + pn < j. In other words, we want to make s[j + p0] < s[p] for some p where i <= p < j thus s[j + p0] will not be the solution as a result.
Now this explanation is a bit verbose, so I'll try to make it simpler for you to understand.
Think of two sequences matching k characters so far and only differ at s[i + k] > s[j + k]. Regardless of the j relative position to i, we can set j to j + k + 1.
For any j2 like j < j2 < j + k, and i2 like i < i2 < i + k and i - i2 + k = j + k - j2 substring [j2, j + k] is still smaller than [i2, i + k]. Now if s[i + k] < s[j + k] then set i to i + k + 1, and when i = j set j to j + 1, thus gets to the final code.
class Solution:
def lastSubstring(self, s: str) -> str:
i, j, k = 0, 1, 0
n = len(s)
while j + k < n:
if s[i+k] == s[j+k]:
k += 1
continue
elif s[i+k] > s[j+k]:
j = j + k + 1
else:
i = max(i + k + 1, j)
j = i + 1
k = 0
return s[i:]
