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 nonempty 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: Four possible ways to split into maximum unique substrings are: ['a', 'b', 'c', 'abc'] & ['a', 'b', 'cab', 'c'] & ['a', 'bca', 'b', 'c'] & ['abc', 'a', 'b', 'c'], all have 4 substrings.
Constraints:

1 <= s.length <= 16

s
contains only lower case English letters.
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.
Code
Here is the code of our algorithm:
Time Complexity
We can split any given string of length n
in 2^n ways. Hence the time complexity will be O(2^n).
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.