Problem

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.

Examples

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.

Solution

Method 1 - Using Backtracking and hashset

Here is the approach:

  1. Backtracking: The idea is to recursively try to split the input string starting from the first character. For each position, we check all possible substrings starting from that position.
  2. Set for Uniqueness: Use a set to keep track of the substrings we have seen so far to ensure all of them are unique.
  3. Recursive Exploration: For each substring, if it is unique, we add it to the set and recursively explore the remaining part of the string.
  4. Maximize the Count: We keep track of t

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
public class Solution {
    /**
    * This method initializes the recursive backtracking method to find
    * the maximum number of unique substrings.
    *
    * @param s The input string.
    * @return The maximum count of unique substrings that the string can be split into.
    */
    public int maxUniqueSplit(String s) {
        return dfs(s, 0, new HashSet<>());
    }

    /**
    * This recursive method performs the depth-first search to explore all possible
    * splits of the string and keeps track of the maximum count of unique substrings.
    *
    * @param s The input string.
    * @param start The starting index for the current recursive call.
    * @param seen A set to keep track of the substrings that have already been seen.
    * @return The maximum count of unique substrings for the current split.
    */
    private int dfs(String s, int start, Set<String> seen) {
        // Base case: if we have reached the end of the string, no more splits can be made.
        if (start == s.length()) {
            return 0;
        }
        
        int maxSplits = 0;
        
        // Iterate through all possible substrings starting at 'start'.
        for (int end = start + 1; end <= s.length(); end++) {
            String substring = s.substring(start, end);
            
            // If the substring has not been seen before, process it.
            if (!seen.contains(substring)) {
                // Add the new substring to the seen set.
                seen.add(substring);
                
                // Recursively calculate the maximum splits for the remaining part of the string.
                maxSplits = Math.max(maxSplits, 1 + dfs(s, end, seen));
                
                // Backtrack: remove the substring from the set to explore other splits.
                seen.remove(substring);
            }
        }
        return maxSplits;
    }
}
Python
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return self.backtrack(s, 0, set())
    
    def backtrack(self, s, start, seen):
        if start == len(s):
            return 0
        
        max_splits = 0
        for end in range(start + 1, len(s) + 1):
            substring = s[start:end]
            if substring not in seen:
                seen.add(substring)
                max_splits = max(max_splits, 1 + self.backtrack(s, end, seen))
                seen.remove(substring)
        
        return max_splits

Complexity

  • ⏰ Time complexity: O(n * 2^n) in the worst case because for each character, we can either include it in an existing substring or start a new substring. This results in an exponential number of ways to split the string. The additional * n comes from the substring operations.
  • 🧺 Space complexity: O(n) because in the worst case, the recursion stack will hold n calls and the set will store n unique substrings.