Split a String Into the Max Number of Unique Substrings - Solution & Explanation
Problem Statement
Given a string s, return the maximum number of unique substrings that the given string can be split into.
You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "ababccc" Output: 5 Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.
Example 2:
Input: s = "aba" Output: 2 Explanation: One way to split maximally is ['a', 'ba'].
Example 3:
Input: s = "aa" Output: 1 Explanation: It is impossible to split the string any further.
Constraints:
-
1 <= s.length <= 16 -
scontains only lower case English letters.
Approach Overview
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.
Approach 1: Backtracking
This approach uses backtracking to explore all possible partitions of the string into unique substrings. We perform a depth-first search (DFS) that tries to form new substrings starting from each character position. If the substring formed is unique, we recursively call the DFS on the remaining substring. We use a set to track the substrings found so far to ensure all splits are unique.
The function maxUniqueSplit uses a helper backtrack that attempts to partition the given string s starting from an index. The index ranges from the current start position to the end of the string. For each possible substring, it checks its uniqueness by verifying against a set seen. If unique, the substring is added to seen, and the function recurses with the remaining part. The end condition is when the start hits the string's length, meaning no more characters are left to process.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time complexity: O(2^n), as for each character, we have a choice of either starting a new substring or extending an existing one.
Space complexity: O(n), for the recursion stack and the set tracking seen substrings.
Approach 2: Dynamic Programming with Bit Masking
This approach uses dynamic programming combined with bit masking to efficiently store unique substrings. With the string's length constraint (≤ 16), each bit in a mask represents whether a character at a position is part of the current substring. This allows us to attempt various splits and ensure uniqueness by tracking substrings in a hash set or array indexed by bit states.
The Python implementation uses a bitmask to track whether a character has been used. dfs iteratively builds substrings and modifies the bitmask to reflect inclusion of new characters. It recursively checks all valid substring combinations for maximum splits by using the current bitmask state as it moves along the input string.
Code
Python
Complexity
Time complexity: O(2^n * n), accounting for combination checks at each character from the bitmask possibilities.
Space complexity: O(n), handling recursion and storage of current substring states.
Approach 3: Backtracking + Pruning
We define a hash table st to store the currently split substrings. Then we use a depth-first search approach to try to split the string s into several unique substrings.
Specifically, we design a function dfs(i), which means we are considering splitting s[i:].
In the function dfs(i), we first check if the number of substrings already split plus the remaining characters is less than or equal to the current answer. If so, there is no need to continue splitting, and we return directly. If i geq n, it means we have completed the splitting of the entire string, and we update the answer to the maximum of the current number of substrings and the answer. Otherwise, we enumerate the end position j (exclusive) of the current substring and check if s[i..j) has already been split. If not, we add it to the hash table st and continue to recursively consider splitting the remaining part. After the recursive call, we need to remove s[i..j) from the hash table st.
Finally, we return the answer.
The time complexity is O(n^2 times 2^n), and the space complexity is O(n). Here, n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking | Time complexity: O(2^n), as for each character, we have a choice of either starting a new substring or extending an existing one. |
| Dynamic Programming with Bit Masking | Time complexity: O(2^n * n), accounting for combination checks at each character from the bitmask possibilities. |
| Backtracking + Pruning | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Hash Set | O(2^n) | O(n) | General solution; best for interviews due to pruning and clear recursion |
| Dynamic Programming with Bit Masking | O(n * 2^n) | O(2^n) | Useful when modeling partitions as binary split positions |
Video Solution
Leetcode 1593. Split a String Into the Max Number of Unique Substrings • Fraz • 23,115 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Split a String Into the Max Number of Unique Substrings easy or hard?
Split a String Into the Max Number of Unique Substrings Python/Java solution
How to solve Split a String Into the Max Number of Unique Substrings in O(n)?
What is the best approach for Split a String Into the Max Number of Unique Substrings?
Is Split a String Into the Max Number of Unique Substrings asked at Google/Amazon/Meta?
What data structure is used in Split a String Into the Max Number of Unique Substrings?
What is the time complexity of Split a String Into the Max Number of Unique Substrings?
Ready to solve this problem?
Practice Split a String Into the Max Number of Unique Substrings with our built-in code editor and test cases.
Practice on FleetCode