Krammer's blog

https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings/ from Google

Classic backtracking problem. When talking about splitting a string, the brute force way is using the backtracking or recursion to reduce the big problem into a smaller subproblem. After reducing the problem into a base problem, we can easily solve this.

經典recursion考題。如果在面試的時候遇到，或是比賽的時候，看到string長度這麼短，就大概知道是暴力recursion。這題主要就是決定在每個點要不要切割取得一個substring，所以每個點有兩種選擇，換算一下時間複雜度會是2^16=65526。看到這個數字就大概知道沒問題。所以就直接recursion暴力法解了。

 1class Solution {
 2public:
 3    int ans;
 4    int N;
 5    void dfs(string& s, unordered_set<string>& vis, int cur) {
 6        if (cur == s.size()) {
 7            ans = max(ans, (int)vis.size());
 8            return;
 9        }
10        for (int i=cur+1; i<=N; i++) {
11            string t = s.substr(cur, i-cur);
12            if (vis.count(t)) continue;
13            vis.insert(t);
14            dfs(s, vis, i);
15            vis.erase(t);
16        }
17    }
18    int maxUniqueSplit(string s) {
19        N = s.size();
20        ans = 1;
21        unordered_set<string> vis;
22        dfs(s, vis, 0);
23        return ans;
24    }
25};

Editorial: LeetCode 1593 Split a String Into the Max Number of Unique Substrings