Partition a String into the Fewest Duplicate-Free Pieces
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Cut lowercase `s` into nonempty contiguous substrings so each character belongs to exactly one piece and no letter repeats within any piece. Return the smallest possible number of pieces.
```cpp
class Solution {
public:
int partitionString(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = "abcaef"
Output: 2
Explanation: Split into "abc" and "aef". One piece would repeat a, so two is minimal.
```
**Example 2:**
```text
Input: s = "zzxyx"
Output: 3
Explanation: The pieces "z", "zxy" and "x" work. A cut is required between the initial two z letters; one more is required between the later x occurrences.
```
### Constraints
- `1 <= s.length <= 100000`.
- s contains lowercase English letters.
### Clarifying Questions
- Must pieces be contiguous? Yes; cutting creates substrings.
- May a letter occur in different pieces? Yes, only repetition within one piece is forbidden.
- Can any input character be omitted? No; every character belongs to exactly one piece.
- Must a partition be returned? No; only its minimum size.
```hint Check the boundary
Compare repeated letters in one piece with repeated letters separated by a cut.
```
Overview: Split a lowercase string into the fewest contiguous pieces with no repeated letter in any piece, using every character exactly once.
