Lexicographically Greatest Contiguous Substring
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Return the lexicographically greatest nonempty contiguous substring of s. Standard lexicographic order treats a proper prefix as smaller than the longer string.
```cpp
class Solution {
public:
string lastSubstring(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = "baca"
Output: "ca"
Explanation: A substring beginning with c beats every substring beginning with a or b, and ca beats c.
```
**Example 2:**
```text
Input: s = "zzaz"
Output: "zzaz"
Explanation: The first suffix starts with zz, beating the other suffixes starting with z followed by a or ending immediately.
```
### Constraints
- The string length is between 1 and 400000.
- It contains lowercase English letters only.
### Contract considerations
The string result is deterministic, even if identical substrings occur at multiple positions.
```hint Read the boundary condition
When two strings agree until one ends, how does the stated lexicographic convention compare them?
```
### Boundary reminders
The string result is deterministic, even if identical substrings occur at multiple positions.
Overview: Lexicographically Greatest Contiguous Substring. Return the lexicographically greatest nonempty contiguous substring of s.