NeetCode #506LC-1593MediumBacktracking
← Back to All Problems#506 · #1593 · Split a String Into the Max Number of Unique Substrings(拆分字符串使唯一子字符串的数目最大)
📌 Problem Statement & Constraints
Given a string
s, return the maximum number of unique non-empty substrings into which s can be split. Constraints: 1 <= s.length <= 16.💡 Core Algorithmic Approaches
- Backtrack over split positions, maintaining a set of substrings already used.
- At each step, try every possible next substring; skip it if it is already in the set.
- When the end is reached, update the maximum count.
- A useful bound: if
len(seen) + remaining_characters <= best, the branch cannot improve the answer.
💻 Benchmark Python3 Implementation
class Solution:
def maxUniqueSplit(self, s: str) -> int:
self.best = 0
n = len(s)
def dfs(start: int, seen: set) -> None:
# prune: even one character per part cannot beat the best
if len(seen) + (n - start) <= self.best:
return
if start == n:
self.best = max(self.best, len(seen))
return
for end in range(start + 1, n + 1):
sub = s[start:end]
if sub in seen:
continue # duplicates are not allowed
seen.add(sub)
dfs(end, seen)
seen.remove(sub) # backtrack
dfs(0, set())
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(2^n * n): there are 2^(n-1) ways to split, each costing O(n) for the slicing.
💾 Space Complexity
O(n) for the recursion and the set.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to remove the substring on backtrack: later branches would see a polluted set.
- Counting all substrings instead of the number of parts: the objective is the number of splits.
- Skipping the length-based pruning: the search space is exponential without it.
- Allowing empty substrings: each part must be non-empty, hence
range(start + 1, n + 1).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.