Katkat
Back

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

SalesforceSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.