Katkat
Back

Delete One Character Type to Minimize Unique Segments

SalesforceSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Determine which single character type to delete from a string so that greedily partitioning the remaining characters into substrings with all-unique characters yields the minimum number of segments.

Problem Statement

You are given a string s consisting of lowercase English letters. You must choose exactly one character type (e.g., 'a', 'b', etc.) present in s and delete all of its occurrences.

After removing all occurrences of the chosen character, you must partition the remaining string into the minimum number of contiguous, non-empty segments such that no segment contains duplicate characters.

Return the minimum number of segments required after an optimal choice of character to remove. If removing all occurrences of the chosen character leaves the string empty, return 0.

Function Signature

def min_unique_segments(s: str) -> int:
    pass

Input & Output Format

  • Input: A string s consisting of lowercase English letters ('a' through 'z').
  • Output: An integer representing the minimum number of segments with all-unique characters after deleting all occurrences of exactly one character type present in s.

Constraints

  • 1 <= len(s) <= 2 * 10^5
  • s consists only of lowercase English letters.

Examples

Example 1

Input: s = "abacaba"
Output: 2
Explanation:
- If we delete 'a', the remaining string is "bcb". Partitioning into segments with unique characters gives ["bc", "b"] (2 segments).
- If we delete 'b', the remaining string is "aacaa", requiring segments ["a", "ac", "a", "a"] (4 segments).
- If we delete 'c', the remaining string is "abaaba", requiring 4 segments.
The minimum number of segments is 2 (achieved by deleting 'a').

Example 2

Input: s = "aaaa"
Output: 0
Explanation:
The only character present is 'a'. Deleting all occurrences of 'a' leaves an empty string, which requires 0 segments.

Example 3

Input: s = "abcbade"
Output: 2
Explanation:
Deleting 'b' yields "acade", which can be partitioned into ["ac", "ade"] (2 segments).

Edge Cases

  • Strings where all characters are identical: result should be 0.
  • Strings where all characters are already distinct: removing any character leaves a string of distinct characters, requiring 1 segment.
  • Highly repetitive alternating strings (e.g., "abababab").

Hints

Hint 1

Notice that the alphabet size is small (at most 26 unique characters in lowercase English).

Hint 2

For any fixed string, the minimum number of segments with no duplicate characters can be found greedily: extend the current segment until a repeated character is encountered, then start a new segment.

Hint 3

Since there are at most 26 candidate characters to remove, you can evaluate the greedy partition count for each candidate in O(N) time and take the minimum.

Follow-up questions

  • How would you return the actual segment boundary indices of the optimal solution instead of just the minimum count?
  • What if you were allowed to delete up to two distinct character types instead of just one?
  • How would you adapt your approach if the alphabet size was large (e.g., Unicode) and checking all present characters individually became too slow?