Split a String Into the Max Number of Unique Substrings

Problem Description

Ah, the classic dilemma of splitting a string into the maximum number of unique substrings. It’s like trying to divide a pizza among friends without anyone getting the same slice twice. You want to maximize the number of unique pieces, but everyone has their favorite toppings!

In this problem, you are given a string s, and your task is to split it into the maximum number of unique substrings. If you think this is easy, just remember that your friends will always want the same slice, and you’ll end up with a lot of leftovers.

Code Solution


class Solution {
  public int maxUniqueSplit(String s) {
    dfs(s, 0, new HashSet<>());
    return ans;
  }

  private int ans = 0;

  private void dfs(final String s, int start, Set seen) {
    if (start == s.length()) {
      ans = Math.max(ans, seen.size());
      return;
    }

    for (int i = start + 1; i <= s.length(); ++i) {
      final String cand = s.substring(start, i);
      if (seen.contains(cand))
        continue;
      seen.add(cand);
      dfs(s, i, seen);
      seen.remove(cand);
    }
  }
}

Approach

The approach used in this solution is a classic Depth-First Search (DFS). The algorithm explores all possible substrings starting from each index of the string. It keeps track of the unique substrings using a HashSet. When it reaches the end of the string, it updates the maximum count of unique substrings found so far.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(2^N) in the worst case, where N is the length of the string.
Space Complexity	O(N) for the recursion stack and the `HashSet` used to store unique substrings.

Real-World Example

Imagine you are at a buffet with a variety of dishes. You want to try as many different dishes as possible without repeating any. Each dish represents a substring, and your goal is to maximize the number of unique dishes you can sample. Just like in the problem, if you keep going back for the same dish, you’ll miss out on trying something new!