⚡Flashcard Drill➔
NeetCode #138LC-2405MediumArrays & Hashing
← Back to All Problems

#138 · #2405 · Optimal Partition of String(子字符串的最优划分)

📌 Problem Statement & Constraints

Given a string s, partition it into the minimum number of substrings such that each letter appears in at most one substring. Return that minimum number. Constraints: 1 <= s.length <= 10^5, lowercase letters.

💡 Core Algorithmic Approaches

  1. The constraint means no letter may be split across two parts, so once a letter has appeared in the current part, it must not appear again in a later part.
  2. Greedy: extend the current part as long as it does not introduce a repeated letter.
  3. When a character repeats, close the current part and start a new one containing just that character.
  4. The greedy is optimal because any valid partition must cut at or before the first repetition, and cutting as late as possible can never increase the number of parts.

💻 Benchmark Python3 Implementation

class Solution:
    def partitionString(self, s: str) -> int:
        seen = set()
        parts = 1
        for ch in s:
            if ch in seen:                 # would repeat -> close the part
                parts += 1
                seen = {ch}
            else:
                seen.add(ch)
        return parts

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) set operations.
💾 Space Complexity
O(1): the set holds at most 26 characters.

⚠️ Interview Pitfalls & Follow-ups

  • Starting parts at 0: a non-empty string always needs at least one part.
  • Forgetting to seed the new part with the repeated character: it must be included in the new part.
  • Using a count map instead of a set: the check is only whether the character has appeared in the current part, so a set suffices -- but remember to reset it, not accumulate.
  • Trying to look ahead for the optimal cut: the greedy is provably optimal; lookahead is unnecessary.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems