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

• s contains only lower case English letters.

Try it yourself

Try solving this question here: