力扣1177.構(gòu)建回文串檢測

• 因?yàn)樽哟梢?strong>重新排序

  • 因此考慮一下什么情況需要替換字母
  • 1.當(dāng)前有一個字母的數(shù)量為奇數(shù)
    • 需要替換的次數(shù)為0
  • 2.當(dāng)前有二個字母的數(shù)量為奇數(shù)
    • 需要替換的次數(shù)為1 (奇數(shù)個a 奇數(shù)個b 需要將b -> a)
  • 3.當(dāng)前有三個字母的數(shù)量為奇數(shù)
    • 需要替換的次數(shù)為1
  • 4.當(dāng)前有四個字母的數(shù)量為奇數(shù)
    • 需要替換的次數(shù)為2
  • 觀察可以發(fā)現(xiàn) 次數(shù)為[m/2]
    • m為奇數(shù)次數(shù)的字母數(shù)量

•   class Solution {public:vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {int n = s.size(),m = queries.size();//array是個二維 后面是key 前面是valuevector<array<int,26>> sum(n+1);for(int i=0;i<n;i++){sum[i+1] = sum[i];sum[i+1][s[i]-'a'] ++;}vector<bool> res(m);for(int i=0;i<m;i++){auto &query = queries[i];int l = query[0],r = query[1],k = query[2],t = 0;for(int j=0;j<26;j++)t += (sum[r+1][j] - sum[l][j]) % 2;res[i] = t / 2 <= k;}return res;}};