leetcode 5520. 拆分字元串使唯一子字元串的數目最大（C++）

給你一個字元串 

s

 ，請你拆分該字元串，并傳回拆分後唯一子字元串的最大數目。

字元串 

s

 拆分後可以得到若幹 非空子字元串 ，這些子字元串連接配接後應當能夠還原為原字元串。但是拆分出來的每個子字元串都必須是 唯一的 。

注意：子字元串 是字元串中的一個連續字元序列。

示例 1：

輸入：s = "ababccc"
輸出：5
解釋：一種最大拆分方法為 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 這樣拆分不滿足題目要求，因為其中的 'a' 和 'b' 都出現了不止一次。
      

示例 2：

輸入：s = "aba"
輸出：2
解釋：一種最大拆分方法為 ['a', 'ba'] 。
      

示例 3：

輸入：s = "aa"
輸出：1
解釋：無法進一步拆分字元串。
      

提示：

• 1 <= s.length <= 16

• s

   僅包含小寫英文字母

C++

class Solution {
public:
    void dfs(string& s, int& res, unordered_map<string,int>& vec, string& tmp, int start)
    {
        if(start==s.size())
        {
            res=max(res,(int)vec.size());
            return;
        }
        for(int i=start;i<s.size();i++)
        {
            tmp+=s[i];
            if(vec.find(tmp)==vec.end())
            {
                vec[tmp]=1;
                string ss=tmp;
                tmp="";
                dfs(s,res,vec,tmp,i+1);
                vec.erase(ss);
                tmp=ss;
            }
        }
    }
    
    int maxUniqueSplit(string s) 
    {
        int n=s.size();
        int res=0;
        unordered_map<string,int> vec;
        string tmp;
        dfs(s,res,vec,tmp,0);
        return res;
    }
};