668. Optimal Partition of String
You are given a string s of lowercase English letters. Cut s into one or more contiguous pieces so that no letter appears more than once inside any single piece. Every character of s must land in exactly one piece.
Return the minimum number of pieces such a cut can produce.
For instance, "cabbage" can be cut as "cab" + "bage" — both pieces are duplicate-free — but it can never stay whole (the letters a and b repeat), so the answer there is 2.
Example 1:
Input: s = "cabbage"
Output: 2
Explanation: Cut between the two b's: "cab" | "bage". Each piece has all-distinct letters. One whole piece is impossible because 'a' and 'b' repeat, so 2 is the minimum.
Example 2:
Input: s = "zzzz"
Output: 4
Explanation: A piece may hold at most one 'z', so every character must stand alone: "z" | "z" | "z" | "z".
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of lowercase English letters only.
Hints:
The answer only depends on where pieces end. A piece is only ever forced to close when the next letter already occurs in it — what happens if you never close a piece earlier than that?
Scan once, keeping the letters of the current piece in a set (or a 26-bit mask). On a repeat, bump the piece count and restart the tracker with just the current letter. That is O(n) time and O(1) space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "cabbage"
Expected output: 2