leetcode 1593. 拆分字符串使唯一子字符串的数目最大

Problem: 1593. 拆分字符串使唯一子字符串的数目最大

滚动哈希的，数基=31，取模1e9+111，将字符串看作一个31进制的数字，a表示1，b表示2，然后用回溯的，计算当前子字符串代表的数字，放入集合中，若不在集合内，则可以划分开，若在则需要继续加入子字符串，最后拿到最大的集合长度

Code

class Solution { public: const int mod = 1e9 + 111; int base = 31, n, mx = 1, copy; unordered_set<int> te; string ttt; void dfs(int index, int num) { if(index >= n) { if(te.find(num) == te.end()) { mx = max(mx, (int)te.size() + 1); } return; } if(index > 0 && te.find(num) == te.end()) { te.insert(num); dfs(index + 1, ttt[index] - 'a' + 1); te.erase(num); } dfs(index + 1, (((long long)num * (long long)base)%mod + (ttt[index] - 'a' + 1)) % mod); } int maxUniqueSplit(string s) { ttt = s; n = s.size(); dfs(0, 0); return mx; } };