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
s contains only lower case English letters.
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.
C++
Java
C#
JavaScript
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.
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.
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 | 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. |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Split a String Into the Max Number of Unique Substrings with our built-in code editor and test cases.
Practice on FleetCode