String Left Before the Final Round of Removing Each Letter's First Occurrence
Company: Flexport
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a string `s` of lowercase English letters. One round of the following operation is applied to it again and again until the string becomes empty:
- For every letter from `a` to `z`, in that order, remove the first (leftmost) occurrence of that letter from the current string, if the letter occurs in it.
Return the string as it was immediately before the last round, that is, the string at the start of the round that leaves it empty.
### Function Signature
```python
def string_before_last_round(s: str) -> str:
```
### Rules
- In one round, every distinct letter present in the string loses exactly one occurrence, its leftmost one; letters that do not occur are skipped.
- The characters that remain keep their relative order.
- Because `s` is nonempty, at least one round happens, so the returned string is never empty.
- Return the exact string, with its characters in the order they have in the string at the start of the last round.
### Constraints
- `1 <= len(s) <= 5 * 10^5`
- `s` contains only the letters `a` to `z`.
### Examples
**Example 1**
```text
Input: s = "aabcbbca"
Output: "ba"
```
Round 1 removes the first `a`, the first `b` and the first `c`, leaving `"abbca"`. Round 2 removes the first `a`, `b` and `c` of that string, leaving `"ba"`. Round 3 removes both remaining letters and empties the string, so the answer is `"ba"`.
**Example 2**
```text
Input: s = "abcd"
Output: "abcd"
```
Every letter occurs once, so the first round empties the string.
**Example 3**
```text
Input: s = "cbacab"
Output: "cab"
```
Round 1 removes the first `a` (index 2), the first `b` (index 1) and the first `c` (index 0), leaving `"cab"`; round 2 empties it.
Overview: Repeatedly remove the leftmost occurrence of every letter from a lowercase string and return the string as it stood just before the final round emptied it. It tests careful reasoning about a repeated process, efficiency on inputs of up to half a million characters, and exact ordering of the result.
Read the full Flexport Software Engineer interview experience this question came from
You are given a string `s` of lowercase English letters. One round of the following operation is applied to it again and again until the string becomes empty:
- For every letter from `a` to `z`, in that order, remove the first (leftmost) occurrence of that letter from the current string, if the letter occurs in it.
Return the string as it was immediately before the last round, that is, the string at the start of the round that leaves it empty.
Rules:
- In one round, every distinct letter present in the string loses exactly one occurrence, its leftmost one; letters that do not occur are skipped.
- The characters that remain keep their relative order.
- Because `s` is nonempty, at least one round happens, so the returned string is never empty.
- Return the exact string, with its characters in the order they have in the string at the start of the last round.
Implement `string_before_last_round(s)`.
Example 1:
Input: s = "aabcbbca"
Output: "ba"
Round 1 removes the first `a`, the first `b` and the first `c`, leaving "abbca". Round 2 removes the first `a`, `b` and `c` of that string, leaving "ba". Round 3 removes both remaining letters and empties the string, so the answer is "ba".
Example 2:
Input: s = "cbacab"
Output: "cab"
Round 1 removes the first `a` (index 2), the first `b` (index 1) and the first `c` (index 0), leaving "cab"; round 2 empties it.
Constraints:
- 1 <= len(s) <= 5 * 10^5
- `s` contains only the lowercase English letters `a` to `z`.
- No numeric value crosses the interface; the string length fits in a 32-bit int.
Constraints
- 1 <= len(s) <= 5 * 10^5
- s contains only the lowercase English letters 'a' to 'z'.
Examples
Input: ('aabcbbca',)
Expected Output: 'ba'
Explanation: Source example 1: a and b occur 3 times, c twice; the last a (index 7) and last b (index 5) remain, in index order.
Input: ('abcd',)
Expected Output: 'abcd'
Explanation: Source example 2: every letter occurs once, so the first round empties the string and the whole input is returned.
Hints
- Follow a single letter through the rounds: each round it loses exactly one occurrence, its leftmost remaining one. Which of its occurrences disappears in round k?
- How many rounds happen in total, and which letters can still be present when the final round starts?
- The surviving characters keep their relative order, so the answer is a subsequence of the original string.