class Solution {
    int maxSplit = 1;

    public int maxUniqueSplit(String s) {
        Set<String> set = new HashSet<>();
        backtrack(0, 0, s, set);
        return maxSplit;
    }

    public void backtrack(int index, int split, String s, Set<String> set) {
        int length = s.length();

        if (index >= length) {
            maxSplit = Math.max(maxSplit, split);
        } else {
            for (int i = index; i < length; i++) {
                if (set.size() + (length - index + 1) < maxSplit) {
                    return;
                }

                String substring = s.substring(index, i + 1);

                if (!set.contains(substring)) {
                    set.add(substring);
                    backtrack(i + 1, split + 1, s, set);
                    set.remove(substring);
                }
            }
        }
    }
}