⚡Flashcard Drill➔
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

  1. Backtrack over split positions, maintaining a set of substrings already used.
  2. At each step, try every possible next substring; skip it if it is already in the set.
  3. When the end is reached, update the maximum count.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems