Introduction

In this blog post, we will explore how to solve the LeetCode problem "1163" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's the breakdown of the solution:

• Identify Potential Starts: The algorithm iterates through the string, comparing each character with the character at the current "best" starting position. If a character is greater than the current best starting character, it becomes the new best. If it's equal, we compare the substrings starting from both positions.
• Lexicographical Comparison: The core of the efficiency lies in only comparing substrings when necessary (when characters are equal). This avoids unnecessary string comparisons.

• Return Last Substring: After iterating through the entire string, the substring starting from the "best" position is the lexicographically largest.

• Time & Space Complexity: O(n) time, O(1) space.

Code

    def last_substring(s: str) -> str:
    """
    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.
    """
    n = len(s)
    best_start = 0
    for i in range(1, n):
        if s[i] > s[best_start]:
            best_start = i
        elif s[i] == s[best_start]:
            k = 1
            while i + k < n and best_start + k < n and s[i + k] == s[best_start + k]:
                k += 1

            if i + k < n and best_start + k < n and s[i + k] > s[best_start + k]:
                best_start = i
            elif best_start + k >=n and i+k < n:
                pass #best_start remains the same
            elif i + k >=n and best_start + k < n:
                pass # best_start remains the same
            elif i+k < n and best_start + k >= n:
                best_start = i
            #else: i+k>=n and best_start+k >=n. Do nothing

    return s[best_start:]