Delete One Character Type to Minimize Unique Segments
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Problem
Implement `min_unique_segments_after_deletion(s)` for a nonempty lowercase English string.
Choose exactly one character value that appears in `s` and delete every occurrence of that character. Partition the remaining string, in order, into the minimum number of nonempty contiguous segments such that no segment contains a repeated character. Return the smallest segment count obtainable over all choices of deleted character. If deletion leaves the empty string, return `0`.
## Constraints
- `1 <= len(s) <= 200,000`
- `s` contains only `a` through `z`.
## Examples
- `"avcccde"` returns `1`: delete `c`, leaving `"avde"`, whose characters are all distinct.
- `"aaaa"` returns `0`: delete `a`.
- `"abca"` returns `1`: delete `a`, leaving `"bc"`.
## Clarifications
Deleting a character means deleting all of its occurrences, not one selected occurrence. Segments must cover the entire remaining string without reordering it.
## Hint
For a fixed deleted character, scan left to right and start a new segment exactly when the next character already exists in the current segment. The alphabet size is fixed and small.
## Interview Follow-ups
- Return which character should be deleted and the segment boundaries.
- Allow deleting up to two distinct character values.
- Generalize to a large or streaming alphabet.
Quick Answer: Choose one lowercase character value to remove everywhere, then minimize the number of ordered nonempty segments needed so that no segment repeats a character. Account for deleting the entire string, large inputs, exact all-occurrence semantics, segment-boundary output, two-character deletion, and larger or streaming alphabets.
Given a nonempty lowercase English string `s`, choose exactly one character value that occurs in `s` and delete every occurrence of that value. Keep all remaining characters in their original relative order. Partition the remainder into the minimum number of nonempty contiguous segments such that no segment contains a repeated character. Return the smallest segment count over all permitted deletion choices. If the deletion leaves the empty string, return `0`.
Examples:
- `"avcccde"` returns `1`: deleting `c` leaves `"avde"`, whose characters are all distinct.
- `"aaaa"` returns `0`: deleting `a` leaves the empty string.
- `"abca"` returns `1`: deleting `a` leaves `"bc"`.
Constraints
- 1 <= len(s) <= 200,000.
- s contains only lowercase English letters 'a' through 'z'.
- The deleted character value must occur in s, and every occurrence of it is removed.
- Remaining characters preserve their relative order, and every segment is nonempty and contiguous.
Examples
Input: ('avcccde',)
Expected Output: 1
Explanation: Deleting every 'c' leaves 'avde', whose four characters fit in one segment.
Input: ('aaaa',)
Expected Output: 0
Explanation: The only permitted choice deletes all four 'a' characters, so the remainder is empty.
Hints
- The alphabet has only 26 values, so consider the remainder produced by each permitted deleted character.
- For one fixed remainder, a repeated character cannot stay in the same segment as its earlier occurrence.