Last Substring in Lexicographical Order — LeetCode 1163 Python Solution

The problem

Given a string s, return the last substring of s in lexicographical order.

Example

Input

s = "abab"

Output

"bab"

Explanation

The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Python solution

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:]

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1163. Last Substring in Lexicographical Order is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems