1593. Split a String Into the Max Number of Unique Substrings

Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

 Example 1:

Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.

Example 2:

Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].

Example 3:

Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.

 Constraints:

• 1 <= s.length <= 16

• s contains only lower case English letters.

C++

• class Solution {
  public:
      unordered_set<string> vis;
      string s;
      int ans = 1;
  
      int maxUniqueSplit(string s) {
          this->s = s;
          dfs(0, 0);
          return ans;
      }
  
      void dfs(int i, int t) {
          if (i >= s.size()) {
              ans = max(ans, t);
              return;
          }
          for (int j = i + 1; j <= s.size(); ++j) {
              string x = s.substr(i, j - i);
              if (!vis.count(x)) {
                  vis.insert(x);
                  dfs(j, t + 1);
                  vis.erase(x);
              }
          }
      }
  };

JAVA

• class Solution {
      private Set<String> vis = new HashSet<>();
      private int ans = 1;
      private String s;
  
      public int maxUniqueSplit(String s) {
          this.s = s;
          dfs(0, 0);
          return ans;
      }
  
      private void dfs(int i, int t) {
          if (i >= s.length()) {
              ans = Math.max(ans, t);
              return;
          }
          for (int j = i + 1; j <= s.length(); ++j) {
              String x = s.substring(i, j);
              if (vis.add(x)) {
                  dfs(j, t + 1);
                  vis.remove(x);
              }
          }
      }
  }

PYTHON

• class Solution:
      def __init__(self):
          self.vis = set()
          self.s = ""
          self.ans = 1
  
      def maxUniqueSplit(self, s: str) -> int:
          self.s = s
          self.dfs(0, 0)
          return self.ans
  
      def dfs(self, i: int, t: int) -> None:
          if i >= len(self.s):
              self.ans = max(self.ans, t)
              return
          for j in range(i + 1, len(self.s) + 1):
              x = self.s[i:j]
              if x not in self.vis:
                  self.vis.add(x)
                  self.dfs(j, t + 1)
                  self.vis.remove(x)