We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Last Substring in Lexicographical Order

Number: 1133

Difficulty: Hard

Paid? No

Companies: Amazon, MathWorks

Problem Description

Given a string s, return the last substring of s in lexicographical order. The challenge is to find an efficient method to compute the answer without generating and comparing all possible substrings.

Key Insights

  • The problem is to determine the lexicographically largest substring.
  • A brute-force approach generating all substrings would be too slow given the input constraints.
  • A two-pointer approach can efficiently compare candidate substrings without extra space.
  • The idea is to use one pointer as the start of the current best candidate and another pointer to scan possible candidates.
  • When comparing equal characters, use a counter to determine differences, then adjust pointers based on the comparison outcome.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

The solution uses a two-pointer technique. One pointer (start) designates the beginning of the current best candidate substring, while another pointer (i) scans through the string. A counter (k) is used to compare characters of the candidate substrings. If the character at the candidate pointer is less than the character at the current pointer, update the start pointer and reset the counter. Otherwise, skip ahead appropriately. This method avoids the need to generate all substrings and operates in linear time with constant extra space.

Code Solutions

def last_substring(s: str) -> str:
    n = len(s)
    start, i, k = 0, 1, 0
    # Loop until the second pointer and k are within the string
    while i + k < n:
        # If the characters match, increment k to compare the next characters
        if s[start + k] == s[i + k]:
            k += 1
        # If the candidate substring is smaller, update start to the new candidate position
        elif s[start + k] < s[i + k]:
            start = max(start + k + 1, i)
            i = start + 1
            k = 0
        # Otherwise, skip the current candidate and move pointer i ahead
        else:
            i = i + k + 1
            k = 0
    return s[start:]

# Test examples
print(last_substring("abab"))      # Output: "bab"
print(last_substring("leetcode"))  # Output: "tcode"
← Back to All Questions