Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1163.html

1163. Last Substring in Lexicographical Order (Hard)

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

 

Example 1:

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

Example 2:

Input: "leetcode"
Output: "tcode"

 

Note:

  1. 1 <= s.length <= 10^5
  2. s contains only lowercase English letters.

Companies:
Mathworks

Related Topics:
String

Solution 1. Brute Force

First, find the greatest character, with which the answer must start.

Push all the indexes of that character into a candidate vector, which are all the possible solutions.

Note that considering the case "a............a", we only push if the character before the current index is not also the greatest character. This is because in that case, the previous index must yield better result than the current index (For example, for "ddab" and "dab", we don’t need to consider "dab").

Now we have all the possible start indexes, we continue to look at the 2nd, 3rd, … characters after the start indexes.

  • If this start index can’t afford len characters after it but others can, it should be ignored.
  • For each start indexes n, we look at the s[n + len], and find the greatest character. We only keep the start indexes that has the greatest character we just found at s[n + len].

As we extending the len, the size of the available start indexes gets smaller and smaller until it becomes 1. The last start index left is the start index of the answer.

// OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/
// Time: O(VL) where V is the length of `v` and L is the max possible `len`.
//       It is strictly smaller than O(N^2)
// Space: O(N)
class Solution {
public:
    string lastSubstring(string s) {
        int start = 0, N = s.size();
        for (int i = 0; i < N; ++i) {
            if (s[i] > s[start]) start = i;
        }
        vector<int> v;
        for (int i = start; i < N; ++i) {
            if (s[i] == s[start] && (i == 0 || s[i - 1] != s[start])) v.push_back(i);
        }
        for (int len = 1; len <= N && v.size() > 1; ++len) {
            vector<int> next;
            char c = 'a';
            for (int n : v) {
                if (n + len >= N || s[n + len] < c) continue;
                if (s[n + len] > c) {
                    next.clear();
                    c = s[n + len];
                }
                next.push_back(n);
            }
            v = next;
        }
        return s.substr(v[0]);
    }
};

Solution 2. Brute Force

For a substring A and all its prefix substrings, A must be the one lexicographically largest. So we don’t need to consider the prefix substrings of A.

So for this question, we only need to consider the N suffix substrings of s.

We just brute-forcely compare all the suffix strings.

One optimization we do for the "a.....a" case is if (i + j == N) break. My reasoning is as follows.

When i + j == N, the string i is of pattern ABA, where j is the start index of the second string segment A.

Example

 i           j
[ddac](abac)[ddac]

Note that string A and B won’t have any character greater than s[i] because otherwise i will be moved to that greater character first.

Since we’ve already moved to s[j], it means there is no better solution between i+1 and j - 1. So we only need to think about the indexes after j. For each k in [j + 1, N), we can find a counterpart t in [i + 1, i + N - j), and string t must be better than string k since they have the same prefix and string t is longer. And because string t is no better than string i, so we can ignore all indexes after j.

Note that this optimization can’t pass test case "a....ab" though.

// OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/
// Time: O(N^2)
// Space: O(1)
// Ref: https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/360957/C%2B%2B-Brute-Force
class Solution {
public:
    string lastSubstring(string s) {
        int start = 0, N = s.size(), j;
        for (int i = 1; i < N; ++i) {
            for (j = 0; i + j < N; ++j) {
                if (s[start + j] == s[i + j]) continue;
                start = s[start + j] > s[i + j] ? start : i;
                break;
            }
            if (i + j == N) break;
        }
        return s.substr(start);
    }
};

Solution 3. Brute Force

Same idea as Solution 2 but with different optimization.

We skip the start index i if both s[i] and s[i - 1] are the same as s[start] where start is the best start index currently found.

It’s because in that case string i - 1 must be lexicographically larger than string i.

This solution can pass the test case "a....ab".

// OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    string lastSubstring(string s) {
        int start = 0, N = s.size();
        for (int i = 1; i < N; ++i) {
            if (s[i] == s[start] && s[i - 1] == s[start]) continue;
            for (int j = 0; i + j < N; ++j) {
                if (s[start + j] == s[i + j]) continue;
                start = s[start + j] > s[i + j] ? start : i;
                break;
            }
        }
        return s.substr(start);
    }
};

  • class Solution {
    public String lastSubstring(String s) {
        char maxChar = 'a';
        int length = s.length();
        int index = length - 1;
        for (int i = length - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c > maxChar) {
                index = i;
                maxChar = c;
            } else if (c == maxChar) {
                if (i > 0 && c == s.charAt(i - 1))
                    continue;
                int temp = index;
                index = i;
                for (int j = i, k = temp; j < length && k < length; j++, k++) {
                    if (s.charAt(j) < s.charAt(k)) {
                        index = temp;
                        break;
                    } else if (s.charAt(j) > s.charAt(k))
                        break;
                }
            }
        }
        return s.substring(index);
    }
}

  • // OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/
// Time: O(N^2)
// Space: O(1)
// Ref: https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/360957/C%2B%2B-Brute-Force
class Solution {
public:
    string lastSubstring(string s) {
        int start = 0, N = s.size(), j;
        for (int i = 1; i < N; ++i) {
            for (j = 0; i + j < N; ++j) {
                if (s[start + j] == s[i + j]) continue;
                start = s[start + j] > s[i + j] ? start : i;
                break;
            }
            if (i + j == N) break;
        }
        return s.substr(start);
    }
};

  • # 1163. Last Substring in Lexicographical Order
# https://leetcode.com/problems/last-substring-in-lexicographical-order/

class Solution:
    def lastSubstring(self, s: str) -> str:
        biggest = max(s)
        res = ""
        
        for i,c in enumerate(s):
            if c == biggest:
                res = max(res, s[i:])
        
        return res
        


  • func lastSubstring(s string) string {
	i, n := 0, len(s)
	for j, k := 1, 0; j+k < n; {
		if s[i+k] == s[j+k] {
			k++
		} else if 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:]
}

  • function lastSubstring(s: string): string {
    const n = s.length;
    let i = 0;
    for (let j = 1, k = 0; j + k < n; ) {
        if (s[i + k] === s[j + k]) {
            ++k;
        } else if (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.slice(i);
}

All Problems

All Solutions