Quick Overview

A string problem: delete every occurrence of one chosen lowercase letter, then split what remains into the fewest contiguous pieces with no repeated letters. It tests reasoning about optimal partitions, evaluating every deletion choice efficiently, and edge cases on strings up to 200,000 characters.

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

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

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 ```python 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.

Overview: A string problem: delete every occurrence of one chosen lowercase letter, then split what remains into the fewest contiguous pieces with no repeated letters. It tests reasoning about optimal partitions, evaluating every deletion choice efficiently, and edge cases on strings up to 200,000 characters.

Read the full Salesforce Software Engineer interview experience this question came from

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. ### 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. The result is an integer from `0` to `len(s)` inclusive and is uniquely determined by the input. ### Constraints - `1 <= len(s) <= 200000` - `s` contains only the letters `'a'` to `'z'`. - The result is an integer from `0` to `len(s)` inclusive, so it fits in a 32-bit signed integer. ### 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.

Constraints

  • 1 <= len(s) <= 200000
  • s contains only the lowercase letters 'a' to 'z'
  • The result is an integer from 0 to len(s) inclusive (fits in a 32-bit signed integer)

Examples

Input: ('abacaba',)

Expected Output: 2

Input: ('zzzz',)

Expected Output: 0

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.

Loading coding console...

Show the approach

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)