Remove Duplicate Letters Lexicographically
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Remove Duplicate Letters Lexicographically
Given a lowercase string, remove repeated occurrences so that every distinct letter appears exactly once. The returned string must be a subsequence of the input and must be the lexicographically smallest result among all subsequences that contain each distinct letter exactly once.
### Function Signature
```python
def remove_duplicate_letters(text: str) -> str:
...
```
### Input
- `text` contains only lowercase English letters.
### Output
Return the lexicographically smallest valid subsequence containing each distinct input letter exactly once.
### Constraints
- `1 <= len(text) <= 100_000`
### Examples
```text
Input: "bcabc"
Output: "abc"
Input: "cbacdcbc"
Output: "acdb"
Input: "aaaa"
Output: "a"
```
### Clarifications
- Relative order must be preserved because the result is a subsequence.
- Lexicographic comparison uses normal lowercase letter order.
- A solution should handle the largest input without enumerating subsequences.
Quick Answer: Remove repeated lowercase letters so each distinct character appears once in the lexicographically smallest valid subsequence. A monotonic stack, remaining-occurrence information, and a membership set produce a linear-time solution without enumerating subsequences.
Remove repeated occurrences from a lowercase string so every distinct letter appears exactly once. The result must remain a subsequence and be lexicographically smallest among all valid subsequences.
Constraints
- The input contains only lowercase English letters.
- Every distinct input letter appears exactly once in the result.
- The result must be a subsequence of the input.
- The input length is at least one and at most 100,000.
- Do not enumerate subsequences.
Examples
Input: ("bcabc",)
Expected Output: 'abc'
Explanation: The later b and c allow the leading larger letters to be replaced.
Input: ("cbacdcbc",)
Expected Output: 'acdb'
Explanation: The canonical example preserves feasibility while minimizing the prefix.
Hints
- Track the last position of each character.
- Maintain a stack of characters already selected.
- Pop a larger stack top only when it appears again later.