Problem Description

You are given a string s and need to find the maximum number of unique substrings you can split it into.

The rules for splitting are:

• You can split the string into any list of non-empty substrings
• When concatenated together, these substrings must form the original string
• All substrings in your split must be unique (no duplicates allowed)
• A substring is defined as a contiguous sequence of characters within the string

For example, if s = "ababccc", one possible split could be ["a", "b", "ab", "ccc"] which gives us 4 unique substrings. Another split could be ["a", "ba", "bccc"] which gives us 3 unique substrings. The goal is to find the split that maximizes the number of unique substrings.

The solution uses backtracking with pruning. It maintains a set st to track the current unique substrings being used in the split. The dfs(i) function explores all possible ways to split the string starting from index i. For each position, it tries different substring lengths s[i:j], and if that substring hasn't been used yet, it adds it to the set and recursively explores splitting the rest of the string. The pruning optimization checks if the current path can possibly beat the best answer found so far - if not, it abandons that path early.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves string manipulation and splitting, not nodes and edges as in graph problems.

Need to solve for kth smallest/largest?

• No: We're looking for the maximum number of unique substrings, not the kth smallest or largest element.

Involves Linked Lists?

• No: The problem deals with strings, not linked list data structures.

Does the problem have small constraints?

• Yes: The string length is typically small (usually up to 16 characters based on LeetCode constraints), and we need to explore all possible ways to split the string into unique substrings. The exponential nature of trying all possible splits is manageable with small constraints.

Brute force / Backtracking?

• Yes: We need to explore all possible ways to split the string, trying different substring combinations. At each position, we make a choice (where to end the current substring), explore that path recursively, and then backtrack to try other possibilities. This is a classic backtracking pattern where we:
  • Make a choice (select a substring)
  • Add it to our current solution if it's unique
  • Recursively explore the remaining string
  • Remove the substring (backtrack) to try other options

Conclusion: The flowchart correctly leads us to use a Backtracking approach, which matches the solution's implementation using DFS with a set to track unique substrings and recursive exploration of all possible splits.

Intuition

When we need to find the maximum number of unique substrings, we face a decision-making problem at each position in the string: where should the current substring end? Since we want to maximize the count and all substrings must be unique, we need to explore all possible valid splits.

Think of it like cutting a ribbon into pieces where no two pieces can be identical. At each position, we have multiple choices - we could cut immediately after the current character, or after two characters, or three, and so on. Each choice leads to a different configuration of the remaining string.

The key insight is that this is an optimization problem with constraints (uniqueness) where we need to explore all possibilities. We can't use a greedy approach because taking the shortest possible substring at each step doesn't guarantee the maximum count overall. For example, with "aba", if we greedily take "a" first, we can only get ["a", "ba"] (2 substrings), but if we take "ab" first, we get ["ab", "a"] (also 2 substrings). The optimal solution requires trying both paths.

This naturally leads to a backtracking approach where we:

1. Try each possible substring starting from the current position
2. If it hasn't been used yet, temporarily add it to our solution
3. Recursively solve for the remaining string
4. Remove the substring (backtrack) to try other possibilities
5. Keep track of the maximum count achieved across all valid splits

The pruning optimization comes from realizing that if our current path can't possibly beat the best answer we've found so far (current substrings + remaining characters ≤ best answer), we can abandon that path early. This significantly reduces the search space while still guaranteeing we find the optimal solution.

Learn more about Backtracking patterns.

Solution Approach

The implementation uses a backtracking algorithm with a hash set to track unique substrings and pruning to optimize the search.

Data Structures:

• st: A set that stores the currently used unique substrings in our split
• ans: A variable to track the maximum number of unique substrings found so far

Main Algorithm - DFS Function:

The core function dfs(i) explores all possible ways to split the string starting from index i:

1. Pruning Check: if len(st) + len(s) - i <= ans:

   • This checks if the current number of substrings (len(st)) plus the maximum possible substrings from the remaining string (len(s) - i) is less than or equal to our current best answer
   • If true, we can't improve our answer on this path, so we return early

2. Base Case: if i >= len(s):

   • We've processed the entire string
   • Update ans with the maximum of current answer and the size of our unique substring set

3. Recursive Exploration:

   for j in range(i + 1, len(s) + 1):
       if s[i:j] not in st:
           st.add(s[i:j])
           dfs(j)
           st.remove(s[i:j])

   • Try every possible ending position j for a substring starting at i
   • Extract substring s[i:j] and check if it's already been used
   • If unique, add it to the set and recursively process the rest of the string from position j
   • After exploring that path, backtrack by removing the substring from the set

How It Works:

Starting with dfs(0), the algorithm explores a decision tree where each node represents a choice of where to end the current substring. For example, with string "aba":

• First level: try "a" (continue from index 1), "ab" (continue from index 2), or "aba" (complete)
• For each choice, recursively explore all possibilities for the remaining string
• The backtracking ensures we try all combinations while maintaining uniqueness through the set

The pruning optimization is crucial for efficiency - it prevents exploring branches that cannot possibly lead to a better solution than what we've already found, significantly reducing the time complexity for longer strings.

Example Walkthrough

Let's trace through the algorithm with s = "aba" to find the maximum number of unique substrings.

Initial State:

• st = {} (empty set for tracking unique substrings)
• ans = 0 (maximum count found so far)
• Start with dfs(0)

Step 1: dfs(0) - Processing from index 0

• Pruning check: 0 + 3 - 0 = 3 > 0 ✓ Continue
• Try substring s[0:1] = "a":
  • "a" not in st, so add it: st = {"a"}
  • Call dfs(1)

Step 2: dfs(1) - Processing from index 1 with st = {"a"}

• Pruning check: 1 + 3 - 1 = 3 > 0 ✓ Continue
• Try substring s[1:2] = "b":
  • "b" not in st, so add it: st = {"a", "b"}
  • Call dfs(2)

Step 3: dfs(2) - Processing from index 2 with st = {"a", "b"}

• Pruning check: 2 + 3 - 2 = 3 > 0 ✓ Continue
• Try substring s[2:3] = "a":
  • "a" already in st, skip this option
• No valid options, return

Back to Step 2: Continue with next option

• Try substring s[1:3] = "ba":
  • "ba" not in st, so add it: st = {"a", "ba"}
  • Call dfs(3)

Step 4: dfs(3) - Base case reached

• i = 3 >= len(s), so we've used the entire string
• Update ans = max(0, 2) = 2
• Return

Backtrack and continue exploring:

• Remove "ba" from st: st = {"a"}
• Remove "a" from st: st = {}

Step 5: dfs(0) - Try next option from root

• Try substring s[0:2] = "ab":
  • "ab" not in st, so add it: st = {"ab"}
  • Call dfs(2)

Step 6: dfs(2) - Processing from index 2 with st = {"ab"}

• Try substring s[2:3] = "a":
  • "a" not in st, so add it: st = {"ab", "a"}
  • Call dfs(3)
  • Base case: Update ans = max(2, 2) = 2

Continue until all paths explored...

The algorithm also explores ["aba"] which gives only 1 substring, confirming that the maximum is 2 unique substrings, achievable with splits like ["a", "ba"] or ["ab", "a"].

The pruning optimization becomes more effective with longer strings. For instance, if we already found a solution with 5 unique substrings and we're exploring a path with 2 substrings used and only 2 characters remaining, we know this path can't exceed 4 total substrings, so we prune it immediately.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 × 2^n)

The time complexity analysis breaks down as follows:

• The algorithm explores all possible ways to split the string into unique substrings using backtracking
• At each position i, we try all possible substrings starting from i (positions from i+1 to n), giving us up to n choices
• In the worst case, we explore all possible partitions of the string, which can be represented as placing dividers between characters - this gives us 2^(n-1) or O(2^n) possible partitions
• For each recursive call, we perform substring operations s[i:j] and set operations (add/remove/check), where substring creation takes O(j-i) time
• The substring operations across all recursive calls contribute an additional O(n) factor since we're creating substrings of various lengths
• Combining these factors: O(n × n × 2^n) = O(n^2 × 2^n)

Space Complexity: O(n)

The space complexity analysis:

• The recursion stack depth is at most n (when we split the string into individual characters)
• The set st stores unique substrings, and in the worst case contains substrings whose total length doesn't exceed n
• The space for storing substrings in the set is O(n) since we're only keeping one valid partition at a time during the DFS
• Overall space complexity is O(n) for the recursion stack plus O(n) for the set storage, resulting in O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Pruning Logic

A common mistake is implementing the pruning condition incorrectly, which can either cause the algorithm to miss optimal solutions or fail to prune effectively.

Pitfall Example:

# Incorrect: Using >= instead of <=
if len(unique_substrings) + len(s) - start_index >= max_unique_count:
    return

This would prune branches that could potentially lead to better solutions. The correct logic should check if the maximum possible substrings we can get (current unique count + remaining characters) is less than or equal to our current best.

Solution: Always use <= in the pruning condition: if len(unique_substrings) + len(s) - start_index <= max_unique_count:

2. Forgetting to Backtrack (Remove from Set)

One of the most critical mistakes is forgetting to remove the substring from the set after exploring that branch, which breaks the backtracking mechanism.

Pitfall Example:

if substring not in unique_substrings:
    unique_substrings.add(substring)
    backtrack(end_index)
    # Forgot to remove! This will cause incorrect results

Without removing the substring, it remains in the set for subsequent branches, preventing those branches from using the same substring even though they should be independent paths.

Solution: Always ensure the backtracking step is included:

unique_substrings.add(substring)
backtrack(end_index)
unique_substrings.remove(substring)  # Critical backtracking step

3. Off-by-One Errors in Loop Range

Getting the range boundaries wrong is a frequent issue, especially with Python's exclusive upper bound in range().

Pitfall Example:

# Incorrect: Missing the last character
for end_index in range(start_index + 1, len(s)):  # Should be len(s) + 1
    substring = s[start_index:end_index]

This would never consider substrings that end at the last character of the string.

Solution: Use range(start_index + 1, len(s) + 1) to ensure all possible substring endings are considered, including the full remaining string.

4. Not Using Nonlocal for Variable Updates

When updating max_unique_count inside the nested function, forgetting to declare it as nonlocal will create a local variable instead of updating the outer scope variable.

Pitfall Example:

def backtrack(start_index):
    # Missing: nonlocal max_unique_count
    if start_index >= len(s):
        max_unique_count = max(max_unique_count, len(unique_substrings))  # Creates local variable

Solution: Always declare variables that need to be modified in the outer scope:

def backtrack(start_index):
    nonlocal max_unique_count  # Properly declare nonlocal

5. Inefficient String Slicing Without Pruning

Without the pruning optimization, the algorithm explores many unnecessary branches, leading to poor performance on longer strings.

Pitfall Example:

def backtrack(start_index):
    # Missing pruning check - will explore all branches
    if start_index >= len(s):
        max_unique_count = max(max_unique_count, len(unique_substrings))
        return
  
    for end_index in range(start_index + 1, len(s) + 1):
        # ... rest of the code

Solution: Always include the pruning check before the base case to avoid exploring branches that cannot improve the result:

if len(unique_substrings) + len(s) - start_index <= max_unique_count:
    return  # Prune this branch early