Split a String Into the Max Number of Unique Substrings - Video Solutions

Problem Overview: Given a string s, split it into non-empty substrings so that every substring is unique. The goal is to maximize the number of substrings in the split. Each partition must use every character in the string exactly once while ensuring no substring appears more than once.

Approach 1: Backtracking with Hash Set (Time: O(2^n), Space: O(n))

This problem naturally fits backtracking. You explore every possible way to split the string and track which substrings have already been used. Maintain a HashSet (or set) of used substrings. Starting from index i, iterate j from i to the end, creating substring s[i:j+1]. If it is not already in the set, add it, recurse from j+1, and update the maximum count. After recursion, remove the substring to restore the state.

The key insight is pruning invalid states early. The set guarantees substring uniqueness with O(1) average lookup. Because you try every split point, the recursion tree can grow exponentially in the worst case, giving O(2^n) time complexity. Space complexity is O(n) due to recursion depth and the set storing substrings. This approach directly models the problem constraints and performs well for typical input sizes.

Using a hash-based structure is essential. Constant-time membership checks prevent repeated substring usage efficiently, which is why hash tables are part of the core idea.

Approach 2: Dynamic Programming with Bit Masking (Time: O(n * 2^n), Space: O(2^n))

An alternative approach enumerates possible split positions using bit masks. For a string of length n, there are n-1 potential split points. Each mask represents whether a split occurs at a position. Iterate through masks from 0 to 2^(n-1)-1, construct substrings according to the mask, and check whether all generated substrings are unique using a set.

For each mask, scan the string once to build substrings, then verify uniqueness. If all substrings are unique, update the maximum count. This method systematically enumerates partitions rather than exploring them recursively. The complexity becomes O(n * 2^n) because each mask requires scanning the string and performing hash lookups.

This technique is sometimes easier to reason about when you think of the problem as selecting partition boundaries in a string. However, it typically performs worse than backtracking with pruning because it evaluates many invalid partitions that recursion would skip early.

Recommended for interviews: Backtracking with a hash set is the expected solution. It clearly demonstrates recursive exploration, pruning, and set-based uniqueness checks. Interviewers usually want to see you model the search space and eliminate invalid paths efficiently. The bitmask approach proves you understand partition enumeration, but the backtracking strategy shows stronger algorithmic intuition.