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
- 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.
- Greedy: extend the current part as long as it does not introduce a repeated letter.
- When a character repeats, close the current part and start a new one containing just that character.
- 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
partsat 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.