1
class Solution {
2
  int max = 0;
3

4
  public int maxUniqueSplit(String s) {
5
    int n = s.length();
6
    backtrack(s, 0, new HashSet<String>());
7
    return max;
8
  }
9

10
  public void backtrack(String s, int start, Set<String> h) {
11
    if (start == s.length()) {
12
      max = Math.max(max, h.size());
13
    }
14
    String res = "";
15

16
    for (int i = start; i < s.length(); i++) {
17
      res += s.charAt(i);
18
      if (h.contains(res)) continue;
19
      h.add(res);
20
      backtrack(s, i + 1, h);
21
      h.remove(res);
22
    }
23
  }
24
}