Last Substring In Lexicographical Order - Leetcode Solution

The Last Substring In Lexicographical Order problem on LeetCode asks us to find the lexicographically largest substring within a given string. We need to return the starting index of this substring.

Let's break down the problem. We have a string s of length n. We need to find the lexicographically largest substring within this string. To do this, we can keep track of the largest character we have seen so far. If we encounter a new character that is larger than the largest character we have seen so far, we can reset our substring to start from that character.

Let's implement this approach in code:

class Solution {
public:
    int lastSubstring(string s) {
        int n = s.length();
        int largest = 0; // index of largest character seen so far
        for (int i = 1; i < n; i++) {
            if (s[i] > s[largest]) {
                largest = i;
            } else if (s[i] == s[largest]) {
                // check if substring starting at i is larger than substring starting at largest
                int j = i, k = largest;
                while (j < n && s[j] == s[k]) {
                    j++;
                    k++;
                }
                if (j == n) {
                    // reached end of string, substring starting at i is larger
                    return i;
                } else if (s[j] > s[k]) {
                    // substring starting at i is larger
                    largest = i;
                }
            }
        }
        return largest;
    }
};

Let's go through the code step by step. We start by initializing the largest character seen so far to be the first index (line 3). We then loop through the rest of the string (line 4). If we encounter a new character that is larger than the largest character seen so far, we reset our substring to start from this new character (line 6).

If we encounter a character that is equal to the largest character seen so far, we need to compare the substrings starting from that character and the largest character seen so far. We compare the substrings character by character until we find a difference (line 7-10).

If we reach the end of the string while comparing the substrings, it means that the substring starting from the current index is larger than the substring starting from the largest index seen so far (line 11-13). We return the current index as the starting index of the largest substring.

If we find a character that is larger in the substring starting from the current index, it means that the substring starting from the current index is larger than the substring starting from the largest index seen so far (line 14-16). We update the largest character seen so far to be the current index.

At the end of the loop, we return the largest character seen so far as the starting index of the largest substring (line 17).

This solution has a time complexity of O(n), where n is the length of the input string.

1