LeetCode/java/split-a-string-into-the-max-number-of-unique-substrings.java

class Solution {
  private Set<String> seen;
  private int maxCount;

  private void backtrack(String s, int start, int count) {
    if (count + (s.length() - start) <= maxCount) {
      return;
    }

    if (start == s.length()) {
      maxCount = Math.max(maxCount, count);
      return;
    }

    for (int end = start + 1; end <= s.length(); ++end) {
      var sub = s.substring(start, end);
      if (seen.contains(sub)) {
        continue;
      }

      seen.add(sub);
      backtrack(s, end, count + 1);
      seen.remove(sub);
    }
  }

  public int maxUniqueSplit(String s) {
    seen = new HashSet<>();
    maxCount = 0;

    backtrack(s, 0, 0);

    seen = null;
    return maxCount;
  }
}