Code Implementation

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def backtrack(start, seen):
            if start == len(s):
                return 0
            max_count = 0
            for end in range(start + 1, len(s) + 1):
                substr = s[start:end]
                if substr not in seen:
                    seen.add(substr)
                    count = 1 + backtrack(end, seen)
                    max_count = max(max_count, count)
                    seen.remove(substr)
            return max_count
        return backtrack(0, set())
      

class Solution {
public:
    int maxUniqueSplit(string s) {
        unordered_set<string> seen;
        return backtrack(s, 0, seen);
    }
private:
    int backtrack(const string& s, int start, unordered_set<string>& seen) {
        if (start == s.size()) return 0;
        int maxCount = 0;
        for (int end = start + 1; end <= s.size(); ++end) {
            string sub = s.substr(start, end - start);
            if (seen.find(sub) == seen.end()) {
                seen.insert(sub);
                int count = 1 + backtrack(s, end, seen);
                maxCount = max(maxCount, count);
                seen.erase(sub);
            }
        }
        return maxCount;
    }
};
      

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maxUniqueSplit(String s) {
        return backtrack(s, 0, new HashSet<>());
    }
    private int backtrack(String s, int start, Set<String> seen) {
        if (start == s.length()) return 0;
        int maxCount = 0;
        for (int end = start + 1; end <= s.length(); ++end) {
            String sub = s.substring(start, end);
            if (!seen.contains(sub)) {
                seen.add(sub);
                int count = 1 + backtrack(s, end, seen);
                maxCount = Math.max(maxCount, count);
                seen.remove(sub);
            }
        }
        return maxCount;
    }
}
      

var maxUniqueSplit = function(s) {
    function backtrack(start, seen) {
        if (start === s.length) return 0;
        let maxCount = 0;
        for (let end = start + 1; end <= s.length; ++end) {
            let substr = s.substring(start, end);
            if (!seen.has(substr)) {
                seen.add(substr);
                let count = 1 + backtrack(end, seen);
                maxCount = Math.max(maxCount, count);
                seen.delete(substr);
            }
        }
        return maxCount;
    }
    return backtrack(0, new Set());
};
      

Problem Description

Given a string s, split it into the maximum number of non-empty substrings such that every substring is unique (no repeats). Return the maximum number of unique substrings you can obtain from such a split.

• Each substring must be non-empty and unique within the split.
• Splits must cover the entire string s (no characters left unused).
• You cannot reuse any substring in the split.
• Your goal is to maximize the number of substrings in the split.

Example:
Input: s = "ababccc"
Output: 5
Explanation: One optimal split is ["a", "b", "ab", "c", "cc"].

Thought Process

At first glance, the problem seems to require trying every possible way to split the string and counting how many unique substrings each split gives. But with so many possibilities, brute force would be too slow for longer strings.

The challenge is to ensure that every substring in the split is unique. This means, as we split the string, we need to keep track of what substrings we've already used, and avoid using them again.

A naive way would be to generate all possible splits (which is exponential), but we can use backtracking to explore only valid splits and prune those that reuse substrings. Backtracking lets us try a split, remember which substrings we've used, and undo our choices as we explore all options.

To optimize, we use a set to record substrings we've already used in the current path. This way, we avoid unnecessary work and quickly skip invalid splits.

Solution Approach

Let's break down the solution step by step:

1. Use Backtracking:
   • We start at the beginning of the string and try every possible split point (from the next character up to the end).
   • For each possible substring, if it hasn't been used yet, we add it to our "used" set and continue splitting the rest of the string recursively.
2. Track Used Substrings:
   • We use a set (hash set) to store substrings that are already part of the current split. This allows O(1) lookup to check if a substring is unique.
3. Recursion and Base Case:
   • If we reach the end of the string, that means we've made a valid split. We count how many substrings we've used in this path.
   • We keep track of the maximum number of unique substrings found among all possible splits.
4. Backtrack (Undo Choices):
   • After exploring a split, we remove the substring from the set before trying the next possibility. This lets us explore all combinations without overlap.
5. Return the Maximum:
   • After trying all possible splits, we return the highest count of unique substrings found.

This approach efficiently explores only valid splits and avoids unnecessary repeated work by leveraging the set for uniqueness checking.

Example Walkthrough

Let's walk through the example s = "ababccc" step by step:

1. Start with an empty set of substrings, at position 0.
2. Try substrings starting at index 0:
   • "a" (unique): Add "a" to set, move to index 1.
3. At index 1:
   • "b" (unique): Add "b" to set, move to index 2.
4. At index 2:
   • "a" (already used) → skip.
   • "ab" (unique): Add "ab" to set, move to index 4.
5. At index 4:
   • "c" (unique): Add "c" to set, move to index 5.
6. At index 5:
   • "c" (already used) → skip.
   • "cc" (unique): Add "cc" to set, move to index 7 (end).
7. We've reached the end. The split is ["a", "b", "ab", "c", "cc"], which contains 5 unique substrings.
8. The algorithm continues to explore other possible splits, but none yield more than 5 unique substrings.

The answer is 5.

Time and Space Complexity

• Brute-force Approach:
  • There are 2^n-1 ways to split a string of length n (by placing or not placing a split between each pair of characters).
  • For each split, checking uniqueness is O(n), so total time is O(n × 2ⁿ).
• Backtracking (Optimized) Approach:
  • Worst-case is still exponential, because every substring could be unique, but pruning with the set reduces unnecessary work.
  • In practice, the number of recursive calls is much less than 2ⁿ due to the uniqueness constraint.
  • Space complexity is O(n) for the recursion stack and O(n) for the set of used substrings.

Summary

The problem asks for the maximum number of unique substrings you can get by splitting a string. The key insight is to use backtracking to explore all possible splits, while keeping track of which substrings have already been used. By using a set for uniqueness checking and undoing choices as we backtrack, we efficiently search for the optimal solution. The approach is elegant because it leverages recursion and set operations to prune the search space, making it much faster than brute-force for most cases.