Fewest Repeat-Free Pieces After Deleting Every Copy of One Letter

You are given a string s of lowercase English letters. You must perform the following operation exactly once:

• Choose one lowercase English letter and delete every occurrence of it from s. The remaining letters keep their original order.

Then split the resulting string into non-empty, non-overlapping contiguous pieces that together cover the whole string, so that no piece contains the same letter twice.

Return the minimum possible number of pieces, taking the best choice of letter to delete.

Function Signature

def min_segments_after_deletion(s: str) -> int:

Rules

• The chosen letter may be any of the 26 lowercase letters. Choosing a letter that does not occur in s deletes nothing.
• If the deletion removes every character (every letter of s is the same), the result is the empty string, which needs 0 pieces, so the answer is 0.
• Only the number of pieces is returned, not the letter or the pieces.

Constraints

• 1 <= len(s) <= 200000
• s contains only the letters 'a' to 'z'.
• The result is an integer from 0 to len(s) inclusive, and it is uniquely determined by the input.

Examples

Example 1

• Input: s = "abacaba"
• Output: 2
• Explanation: Deleting every a leaves "bcb", which splits into "bc" and "b". Deleting every b leaves "aacaa" and deleting every c leaves "abaaba"; each of those needs 4 pieces, and so does "abacaba" itself, which is what remains after deleting a letter that does not occur.

Example 2

• Input: s = "zzzz"
• Output: 0
• Explanation: Deleting z removes every character, leaving nothing to split.

Example 3

• Input: s = "mississippi"
• Output: 4
• Explanation: Deleting every s leaves "miiippi", which splits into "mi", "i", "ip" and "pi". Deleting any other letter leaves a string that needs 5 pieces.

Delete One Letter, Then Split Into Distinct-Letter Pieces

Hints

1. For a fixed string, is there ever a reason to end a piece before the next letter would repeat inside it?
2. Deleting characters can never force more pieces, so deleting a letter that does not occur is never better than deleting one that does.
3. There are only 26 letters to try. With a 26-bit mask of the letters in the current piece, each try is a single left-to-right scan.

Approach

Fix the deleted letter c and look at the string t that remains. To split t into the fewest pieces with no repeated letter inside a piece, a greedy scan is optimal: keep extending the current piece, and start a new piece only when the next letter already appears in it. Exchange argument: any sub-segment of a valid piece is itself valid, so by induction the greedy's k-th piece ends at or after the k-th piece of any valid split. That means the greedy never uses more pieces than an optimal split. The scan tracks the letters in the current piece with a 26-bit mask. A letter that repeats inside the current piece resets the mask to just that letter and adds one piece. The first kept letter also opens a piece, and an empty t needs 0 pieces. Deleting a letter that does not occur leaves s unchanged. Restricting the greedy split of s to the letters that remain after any real deletion is still a valid split, with no more pieces, so only letters that occur in s need to be tried. The answer is the minimum over those at most 26 scans.

• Time complexity: O(26 * n)
• Space complexity: O(n)