Break a String Into Maximum Number of Unique Substrings

Share

Split string s into maximum number of unique non-empty substrings.

Example 1
Input: s="ababccc" → Output: 5. "a","b","ab","c","cc"
Example 2
Input: s="aba" → Output: 2

Solution Approach

Backtracking: try every possible prefix, add to set if unique, recurse on remainder.

  • Backtracking with a set of used substrings
  • At each step try all prefixes of remaining string
  • If prefix not in set: add to set and recurse
  • Track maximum partitions found
  • Backtrack: remove prefix from set
Java
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 max = -1;
    for (int end = start + 1; end <= s.length(); end++) {
        String sub = s.substring(start, end);
        if (!seen.contains(sub)) {
            seen.add(sub);
            int res = backtrack(s, end, seen);
            if (res != -1) max = Math.max(max, res + 1);
            seen.remove(sub);
        }
    }
    return max;
}
  • Time Complexity: O(2^n)
  • Space Complexity: O(n)