{x}
blog image

Split a String Into the Max Number of Unique Substrings

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.

Solution Explanation: Split a String Into the Max Number of Unique Substrings

This problem asks us to find the maximum number of unique substrings we can split a given string into. The key constraint is that all substrings must be unique.

Approach: Backtracking with Pruning

The most effective approach is backtracking, enhanced with pruning to optimize performance. Backtracking systematically explores all possible ways to split the string, while pruning avoids unnecessary explorations.

Algorithm:

  1. dfs(i) function: This recursive function explores all possible splits starting from index i of the string.

  2. Base Cases:

    • If the current number of unique substrings (len(st) in Python, st.size() in Java/C++/TypeScript) plus the remaining characters is less than or equal to the current maximum (ans), there's no need to continue exploring this branch because it won't yield a better result. This is the pruning step.
    • If i reaches the end of the string (i >= len(s)), it means we've successfully split the entire string into unique substrings. Update ans with the maximum number of substrings found so far.

  3. Recursive Step:

    • Iterate through all possible ending positions j (exclusive) for the current substring s[i:j].
    • Check if the substring s[i:j] is already present in the set st (which tracks unique substrings). If not:
      • Add s[i:j] to st.
      • Recursively call dfs(j) to explore further splits from index j.
      • Remove s[i:j] from st (backtracking step – crucial for exploring other possibilities).

  4. Initialization: Start the backtracking process by calling dfs(0).

Time and Space Complexity Analysis

  • Time Complexity: The worst-case time complexity is O(n * 2n), where n is the length of the string. This is because, in the worst case, we might explore all possible ways to split the string (2n possibilities), and for each split, we need to perform substring operations (O(n)). The pruning significantly reduces the exploration in practice, making it much faster than the theoretical upper bound.

  • Space Complexity: The space complexity is O(n) because the st set (or equivalent data structure) can store at most n substrings. The recursive call stack also contributes to space complexity but is bounded by n in the worst case.

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples in the previous response demonstrate the backtracking algorithm in multiple programming languages. Each version implements the dfs function and the main logic as described above. The use of a set (or unordered_set in C++) efficiently handles the uniqueness constraint. The pruning optimization significantly speeds up the solution.