1
class Solution {
2
 public:
3
  unordered_set<string> st;
4
  int ans = 0;
5
  void dfs(string &s, int idx) {
6
    if (st.size() > ans) ans = st.size();
7
    if (idx >= s.length()) return;
8
    string str = "";
9
    for (int i = idx; i < s.length(); i++) {
10
      str += s[i];
11
      if (st.find(str) == st.end()) {
12
        st.insert(str);
13
        dfs(s, i + 1);
14
        st.erase(str);
15
      }
16
    }
17
  }
18

19
  int maxUniqueSplit(string s) {
20
    dfs(s, 0);
21
    return ans;
22
  }
23
};