leetcode 困难题 1520. 最多的不重叠子字符串

Problem: 1520. 最多的不重叠子字符串

对每种字符得到开始和结束的区间，然后对每种字符的区间内部的字符，计算得到满足题意的最长区间，也就是当前字符和内部字符两者区间的并集，最后按照字符开始索引排序

回溯，得到选择的区间的总长度，选择的个数，个数最大化，若个数相同则选择总长度更小的

Code

class Solution { public: vector<pair<int, int>> ump, tr; vector<int> tmp, ret, mem, same; int m, mxmx = -1, c1, c3, ind, mi = INT_MAX; void update(int cnt, int len) { if(mxmx < cnt) { mxmx = cnt; ret = tmp; mi = len; } else if (mxmx == cnt) { if(mi > len) ret = tmp; } } int dfs( int index, int end, int cnt, int len ) { if(len >= mi) return INT_MIN/100; if(index == m) { update(cnt, len); return 0; } // if(mem[index] > 0) { // tmp.push_back(); // } int r1, r2, mx, sss, eee; for( int i = index; i < tr.size(); i++ ) { sss = tr[i].first; eee = tr[i].second; if( sss > end ) { tmp.push_back(i); r1 = dfs( i + 1, eee, cnt + 1, len + eee - sss + 1) + 1; tmp.pop_back(); if(same[i] < 0) r2 = dfs( i + 1, end, cnt, len); mx = max( { mx, r1, r2 } ); } } // mem[index] = mx; return mx; } vector<string> maxNumOfSubstrings(string s) { ump.assign(26, {-1, -1}); mem.assign(26, -1); int n = s.size(), ch; for( int i = 0; i < n; i++ ) { ch = s[i] - 'a'; if(ump[ch].first < 0) ump[ch].second = ump[ch].first = i; else ump[ch].second = i; } int start, end, key, change = 1; while(change > 0) { change = -1; for(int i = 0; i < 26; i++) { if(ump[i].first < 0) continue; start = ump[i].first; end = ump[i].second; if(end - start <= 1) continue; unordered_set<char> te( s.begin() + ump[i].first + 1, s.begin() + ump[i].second ); for(const char& cc : te) { if(start > ump[cc-'a'].first) { change = 1; start = ump[cc-'a'].first; } if(end < ump[cc-'a'].second) { change = 1; end = ump[cc-'a'].second; } } ump[i] = {start, end}; } } unordered_set<long long> te; for(int i = 0; i < 26; i++) { if(ump[i].first < 0) continue; start = ump[i].first; end = ump[i].second; key = (start << 20) + end; if(te.find(key) != te.end()) continue; tr.push_back(ump[i]); te.insert(key); } sort(tr.begin(), tr.end()); m = tr.size(); same.assign(m, -1); for(int i = 0; i < m; i++) { if(end - start <= 1) { same[i] = 1; continue; } unordered_set<char> te( s.begin() + ump[i].first, s.begin() + ump[i].second); if(te.size() == 1) same[i] = 1; } dfs(0, -1, 0, 0); vector<string> answer; for(int i = 0; i < ret.size(); i++) { ch = ret[i]; answer.push_back( s.substr(tr[ch].first, tr[ch].second - tr[ch].first + 1) ); } return answer; } };