## Problem Given a nonempty string, return its lexicographically greatest nonempty substring. Standard lexicographic order compares the first differing character; when one string is a prefix of another, the longer string is greater. ### Function Contract Implement `maximumSubstring(text)`. ### Constraints & Assumptions - `1 <= len(text) <= 400,000`. - `text` contains lowercase English letters. - Return the substring itself. - An `O(n^2)` list of candidate substrings is too large. ### Clarifying Questions to Ask - Are substrings contiguous? Yes. - Can the answer end before the original string ends? Extending a candidate with the remaining characters cannot make it smaller, so an optimum is always a suffix. - How are equal prefixes compared? The longer string is greater. - Is an empty answer allowed? No. ```hint Compare suffix candidates without materializing them Maintain two possible suffix starts and an offset into their current common prefix. ``` ```hint Discard a block after a mismatch When `text[i + k]` is smaller than `text[j + k]`, starts from `i` through `i + k` cannot beat the suffix at `j`. ``` ### Examples ```text text = "abab" output = "bab" text = "leetcode" output = "tcode" ``` ### Evaluation Focus - Recognizes that the answer can be restricted to suffixes. - Avoids comparing every pair of suffixes from the beginning. - Advances candidates correctly when prefixes overlap. - Runs in `O(n)` time with `O(1)` auxiliary space, excluding the returned string. ### Extensions to Discuss 1. How would a suffix array solve the same task, and at what cost? 2. How does the candidate-elimination proof handle repeated characters? 3. How would locale-aware collation change the assumptions?