Problem statement

Consider every non-empty substring of s and sort them in lexicographic (dictionary) order. Return the substring that comes last.

Comparison is the usual one: the first differing character decides, and a string that is a proper prefix of another comes before it.

Example 1

Input: s = "kairokai"
Output: rokai
Explanation: `r` is the largest letter and occurs once, so the answer is the suffix starting there.

Example 2

Input: s = "zazb"
Output: zb
Explanation: Both `zazb` and `zb` start with `z`; at the second character `b` beats `a`.

Example 3

Input: s = "bbbb"
Output: bbbb

Constraints

• 1 <= s.length <= 4 * 10^5
• s consists of lowercase English letters

Hints for Last Substring in Lexicographical Order

1. Hint 1

   Extending a substring to the right never makes it smaller, so the answer is always a suffix of s.

2. Hint 2

   Comparing all suffixes directly is quadratic. Keep two candidate starts i < j and the length k of their common prefix.

3. Hint 3

   If s[i+k] < s[j+k], no start in i..i+k can win — jump i to max(i + k + 1, j). If s[i+k] > s[j+k], skip j past j + k. Each step discards at least k + 1 starts.

How to solve Last Substring in Lexicographical Order

The answer is the lexicographically largest suffix, and two competing starts can be compared character by character while discarding whole blocks of losing starts at once — the same trick as the minimum-rotation algorithm.

Approach

1. Set i = 0 (best start so far), j = 1 (challenger), k = 0 (matched length).
2. While j + k < n: if s[i+k] == s[j+k], increment k.
3. If s[i+k] < s[j+k]: every start in i..i+k loses to the matching start in j..j+k, so set i = max(i + k + 1, j), j = i + 1, k = 0.
4. If s[i+k] > s[j+k]: by the same argument every start in j..j+k loses, so set j = j + k + 1, k = 0.
5. Return the suffix starting at i.

Why it works

When the suffixes at i and j agree on k characters and then s[i+k] < s[j+k], any start i + p (with p <= k) is beaten by j + p: they share k - p characters and then differ the same way. So all of i..i+k can be dropped; j itself survives as the new best unless it was among the dropped ones. The symmetric case drops j..j+k. Each step removes at least k + 1 candidates, and k only grows while characters match, so the total work is linear.

Complexity

• Time — O(n)
• Space — O(1) besides the returned suffix

Pitfalls

• Sorting or comparing all suffixes is O(n^2) (or worse) — too slow at 4 * 10^5.
• After a loss of i, the new i must be at least j; jumping to i + k + 1 alone can skip past a valid candidate or move before j.
• On an all-equal string like bbbb the whole string wins (longer beats its own prefix).

Reference solution

Python

def lastSubstring(s: str) -> str:
    n = len(s)
    i, j, k = 0, 1, 0
    while j + k < n:
        if s[i + k] == s[j + k]:
            k += 1
        elif s[i + k] < s[j + k]:
            i = max(i + k + 1, j)
            j = i + 1
            k = 0
        else:
            j = j + k + 1
            k = 0
    return s[i:]

Java

public static String lastSubstring(String s) {
    int n = s.length(), i = 0, j = 1, k = 0;
    while (j + k < n) {
        char a = s.charAt(i + k), b = s.charAt(j + k);
        if (a == b) {
            k++;
        } else if (a < b) {
            i = Math.max(i + k + 1, j);
            j = i + 1;
            k = 0;
        } else {
            j = j + k + 1;
            k = 0;
        }
    }
    return s.substring(i);
}

C++

string lastSubstring(string s) {
    int n = s.size(), i = 0, j = 1, k = 0;
    while (j + k < n) {
        if (s[i + k] == s[j + k]) {
            k++;
        } else if (s[i + k] < s[j + k]) {
            i = max(i + k + 1, j);
            j = i + 1;
            k = 0;
        } else {
            j = j + k + 1;
            k = 0;
        }
    }
    return s.substr(i);
}

JavaScript

var lastSubstring = function(s) {
    var n = s.length, i = 0, j = 1, k = 0;
    while (j + k < n) {
        var a = s.charCodeAt(i + k), b = s.charCodeAt(j + k);
        if (a === b) {
            k++;
        } else if (a < b) {
            i = Math.max(i + k + 1, j);
            j = i + 1;
            k = 0;
        } else {
            j = j + k + 1;
            k = 0;
        }
    }
    return s.substring(i);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard