Katkat
Back

Find the Lexicographically Maximum Suffix

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests string manipulation, greedy algorithm design, and efficiency. It requires an O(n) solution to avoid Time Limit Exceeded errors on long strings, as naive O(n^2) comparisons will fail.

Problem Statement

Given a non-empty string s consisting of lowercase English letters, find its lexicographically largest suffix. A suffix is a substring that starts at some index i (0 str: pass


### Constraints
- `1 <= len(s) <= 400,000`
- The string contains only lowercase English characters 'a'-'z'.

### Examples

**Example 1:**
Input: `s = "banana"`
Output: `"nana"`
Explanation: The suffixes are "banana", "anana", "nana", "ana", "na", "a". Comparing these lexicographically, "nana" is the largest.

**Example 2:**
Input: `s = "ababa"`
Output: `"ba"`
Explanation: The suffixes are "ababa", "baba", "aba", "ba", "a". "ba" comes after the others in alphabetical order.

### Edge Cases
- Single character string: "a" returns "a".
- String with identical characters: "aaaaa" returns "aaaaa".
- String where the suffix is the whole string: "z" returns "z".

Hints

Hint 1

Observe that the lexicographically largest suffix must start with the largest character present in the string.

Hint 2

If there are multiple occurrences of the largest character, you need to compare the substrings starting at those positions without building them explicitly.

Hint 3

Consider a two-pointer approach: track the current 'best' starting index and iterate through the string to update it when a potentially larger suffix is found.

Follow-up questions

  • How would your approach change if you needed to find the lexicographically smallest suffix instead of the largest?
  • Can you explain the time and space complexity of your solution in terms of Big O notation?
  • How would you handle this problem if the input was a stream of characters rather than a pre-loaded string?