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 = "aab"
Output: 2
Explanation: Two possible ways to split the given string into maximum unique substrings are: ['a', 'ab'] & ['aa', 'b'], both have 2 substrings; hence the maximum number of unique substrings in which the given string can be split is 2.
Example 2:
Input: s = "abcabc"
Output: 4
Explanation: The string can be cut into at most four pieces that are all different, so the answer is 4. Eight different cuts reach four pieces, among them ['a', 'b', 'c', 'abc'], ['a', 'bca', 'b', 'c'] and ['ab', 'ca', 'b', 'c']. The question asks how many pieces, not how many cuts achieve it.
Constraints:
-
1 <= s.length <= 16 -
scontains only lower case English letters.
Why this is a Backtracking problem
| What the question says | The signal it matches |
|---|---|
| "return the maximum number of unique substrings that the given string can be split into" | you need the best of many arrangements |
| "you must split the substrings such that all of them are unique" | a partial answer can be ruled out early |
| "1 <= s.length <= 16" | the constraints keep the search small, so an exponential walk is expected |
This is the choose where to cut variant: split off a piece, and stop when the piece has been seen before.
The closest alternative. Dynamic Programming, which is the usual answer for a maximum over splits. It does not work here, and the reason is worth knowing. A DP state would have to remember which pieces were already used. That set is part of the state, so nothing can be reused between branches.
So the search is the answer, and the pruning is the uniqueness rule itself. Keep the pieces used so far in a set. Cutting a piece already in the set ends that branch at once. The set must be restored on the way back out, exactly as in Word Search. With at most 16 characters there are 2 to the power 15 cut positions, about 32,768, so the walk finishes comfortably.
Solution
We can use backtracking to solve this problem.
This solution uses a helper function splitAndCount which takes three arguments, the input string s, the current start position and a set set to keep track of the unique substrings that have been split so far. The maxUniqueSplit function calls the splitAndCount function to find the maximum number of unique substrings that the given string can be split into.
The splitAndCount function starts with a base case where it returns the size of the set when the current start position is equal to the length of the input string. This means that all substrings have been processed and the size of the set represents the maximum number of unique substrings.
The function then uses a for loop to iterate through all possible substrings starting from the current start position. For each substring, it checks if the substring is already in the set. If it is not, the substring is added to the set and the function is recursively called with the new start position being the end of the current substring. This continues until all possible substrings have been processed.
After the recursive call, the substring is removed from the set to backtrack. The function keeps track of the maximum number of unique substrings found so far and returns this maximum count when all substrings have been processed.
Algorithm Walkthrough
Let's trace the first example, s = "aab". Move through the steps one at a time:
Step 1. The string "aab" has to be cut into pieces that join back into it, with no two pieces the same, and the question asks for the largest number of pieces. The search tries every possible first piece, then every possible second piece after it, and so on. A piece that has already been used is refused straight away, which is what keeps the search from growing out of hand.
1 of 11
Code
Here is the code of our algorithm:
Time Complexity
A string of length n has n - 1 places where a cut may or may not be made, so there are 2^{n-1} ways to split it. Each one costs O(n) to build and to check against the set of pieces already used, so the time complexity is O(n * 2^n).
The O(2^n) figure often quoted for this question counts the splits and ignores the cost of each one. Either is defensible in an interview as long as you say which you are counting.
Space Complexity
The space complexity will be O(n) as we need to save only one way of splitting the given string while in the recursion, and our recursion tree won't get bigger than O(n) steps too.