leetcode 困难题 1542. 找出最长的超赞子字符串

Problem: 1542. 找出最长的超赞子字符串计算前缀频次和任意子字符串的字符频次需要满足【频次是奇数的个数1】才能形成回文串所以统计任意子字符串的频次得到最大长度ret剪枝的话子字符串的长度需要 ret才行对连续且相等的字符只考虑最开始几个索引和最后面几个索引防止重复计算导致超时的还可以使用位运算来计算异或操作存储频次的奇偶性质不需要记录频次Codeclass Solution { public: int longestAwesome(string s) { vectorint ump(10, 0); int n s.size(), l, i, j; if(n1) return 1; if(n2) { if(s[1]s[0]) return 2; else return 1; } vectorvectorint arr; arr.push_back(ump); char pre -; int cnt 0, ret 0, count 0; vectorint index; setint status{0,1,2}; for(char c : s) { ump[c-0]; arr.push_back(ump); if(pre ! c) { ret max(ret, cnt); if(cnt 2 count-2 0) { status.insert(count-2); } if(cnt 1 count-1 0) { status.insert(count-1); } status.insert(count); if(cnt 1 count1 n) { status.insert(count1); } cnt 1; } else cnt; pre c; count; } int mx 0, odd 0; status.insert(n-1); status.insert(n); for(const int ii : status) index.push_back(ii); for(int l : ump) { mx max(mx, l); if((l1)1) odd; } if(mx 1) return 1; if(odd 1) return n; for(int ii 0; ii index.size(); ii) { i index[ii]; for(int jj index.size()-1; jj 0; jj--) { j index[jj]; if(j - i ret) break; char tmp s[j-1]; mx 0, odd 0; bool find true; for(int w 0; w 10; w) { l arr[j][w]; if(l 0) { l - arr[i][w]; mx max(mx, l); if((l1)1) odd; if(odd 1) { find false; break; } } } if(find) ret max(ret, j - i); } } return ret; } };方案二位运算Codeclass Solution { public: int longestAwesome(string s) { int mask 0; int n s.size(), l, i, j; if(n1) return 1; if(n2) { if(s[1]s[0]) return 2; else return 1; } vectorint arr; arr.push_back(mask); char pre -; int cnt 0, ret 0, count 0; vectorint index; setint status{0,1,2}; for(char c : s) { mask ^ (1(c-0)); arr.push_back(mask); if(pre ! c) { ret max(ret, cnt); if(cnt 2 count-2 0) { status.insert(count-2); } if(cnt 1 count-1 0) { status.insert(count-1); } status.insert(count); if(cnt 1 count1 n) { status.insert(count1); } cnt 1; } else cnt; pre c; count; } int mx 1, odd 0; status.insert(n-1); status.insert(n); for(const int ii : status) index.push_back(ii); odd __builtin_popcount(mask); if(odd 1) return n; for(int ii 0; ii index.size(); ii) { i index[ii]; for(int jj index.size()-1; jj 0; jj--) { j index[jj]; if(j - i ret) break; odd __builtin_popcount(arr[j] ^ arr[i]); if(odd 1) ret max(ret, j - i); } } return ret; } };