Split string s into maximum number of unique non-empty substrings.
Input: s="ababccc" → Output: 5. "a","b","ab","c","cc"
Input: s="aba" → Output: 2
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
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)