Last Substring in Lexicographical Order

hard two pointers string suffix

Problem

Given a string s, return the last substring of s when all of its substrings are sorted in lexicographical order. The answer is always a suffix of s, since any substring is a prefix of some suffix and the lexicographically largest one cannot be cut short.

Inputs = "abab"

Output"bab"

Among all substrings, sorting them gives "a", "ab", "aba", "abab", "b", "ba", "bab". The last one is "bab".

s (lowercase letters)

def last_substring(s):
    i, j, k = 0, 1, 0
    n = len(s)
    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:]

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

class Solution {
    public String lastSubstring(String s) {
        int i = 0, j = 1, k = 0, n = s.length();
        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);
    }
}

string lastSubstring(string s) {
    int i = 0, j = 1, k = 0, n = s.size();
    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);
}

Explanation

The lexicographically largest substring is always a suffix (a tail of the string), so the real task is to find which starting position gives the biggest suffix. Instead of comparing all suffixes from scratch, this solution races two candidates against each other with two pointers i and j plus an offset k.

i marks the current best suffix start and j is a challenger. We compare them character by character at offset k: s[i+k] versus s[j+k]. If they are equal, the suffixes tie so far, so we just grow k to keep comparing further along.

When they differ, one candidate loses. If s[i+k] < s[j+k] then j's suffix is larger, so the new best jumps to i = max(i+k+1, j) with j just after it and k reset. If s[i+k] > s[j+k] then the challenger j loses, so we skip it ahead to j+k+1 and reset k.

Example: s = "abab". Comparing suffix starts, the b at index 1 beats the a at index 0, and the winning start lands at index 1, giving the suffix "bab".

Skipping ahead by k on every mismatch means we never re-scan characters we already cleared, which keeps the whole thing O(n).

Time: O(n) Space: O(1)