Problem

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

Examples

Example 1

1
2
3

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

Example 2

1
2

Input: s = "leetcode"
Output: "tcode"

Constraints

  • 1 <= s.length <= 4 * 10^5
  • s contains only lowercase English letters.

Solution

Method 1 – Two Pointers (Booth’s Algorithm Variant)

Intuition

To find the last substring in lexicographical order, we want the substring that starts at the position of the largest suffix. We can use a two-pointer approach to efficiently find the starting index of this substring by comparing suffixes directly.

Approach

  1. Initialize two pointers i (current best start) and j (candidate start), and an offset k.
  2. Compare characters at s[i + k] and s[j + k]:
    • If they are equal, increment k.
    • If s[i + k] < s[j + k], move i to i + k + 1 (since a better suffix starts at j).
    • If s[i + k] > s[j + k], move j to j + k + 1 (since the current best is still better).
    • If i == j, increment j.
  3. Continue until either pointer reaches the end.
  4. The answer is the substring starting at i.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    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);
                k = 0;
                j = i + 1;
            } else {
                j = j + k + 1;
                k = 0;
            }
        }
        return s.substr(i);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func lastSubstring(s string) string {
    n := len(s)
    i, j, k := 0, 1, 0
    for 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)
            k = 0
            j = i + 1
        } else {
            j = j + k + 1
            k = 0
        }
    }
    return s[i:]
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public String lastSubstring(String s) {
        int n = s.length(), i = 0, j = 1, k = 0;
        while (j + k < n) {
            if (s.charAt(i + k) == s.charAt(j + k)) {
                k++;
            } else if (s.charAt(i + k) < s.charAt(j + k)) {
                i = Math.max(i + k + 1, j);
                k = 0;
                j = i + 1;
            } else {
                j = j + k + 1;
                k = 0;
            }
        }
        return s.substring(i);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun lastSubstring(s: String): String {
        val n = s.length
        var i = 0; var j = 1; var k = 0
        while (j + k < n) {
            if (s[i + k] == s[j + k]) {
                k++
            } else if (s[i + k] < s[j + k]) {
                i = maxOf(i + k + 1, j)
                k = 0
                j = i + 1
            } else {
                j = j + k + 1
                k = 0
            }
        }
        return s.substring(i)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def lastSubstring(self, 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)
                k = 0
                j = i + 1
            else:
                j = j + k + 1
                k = 0
        return s[i:]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn last_substring(s: String) -> String {
        let s = s.as_bytes();
        let n = s.len();
        let (mut i, mut j, mut k) = (0, 1, 0);
        while j + k < n {
            if s[i + k] == s[j + k] {
                k += 1;
            } else if s[i + k] < s[j + k] {
                i = (i + k + 1).max(j);
                k = 0;
                j = i + 1;
            } else {
                j = j + k + 1;
                k = 0;
            }
        }
        String::from_utf8(s[i..].to_vec()).unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    lastSubstring(s: string): string {
        const n = s.length;
        let 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 = Math.max(i + k + 1, j);
                k = 0;
                j = i + 1;
            } else {
                j = j + k + 1;
                k = 0;
            }
        }
        return s.slice(i);
    }
}

Complexity

  • ⏰ Time complexity: O(n), since each character is compared at most twice.
  • 🧺 Space complexity: O(1), only pointers and counters are used.