【Leetcode】1177. Can Make Palindrome from Substring

题目地址：

https://leetcode.com/problems/can-make-palindrome-from-substring/

给定一个长$n$的字符串$s$，再给定若干询问，每个询问的格式为$(l,r,k)$，问是否将$s[l:r]$中至多修改$k$个字符，可以使得其重排之后能成为回文串。返回所有询问的答案。题目保证$s$只含英文小写字母。

可以先用前缀和对求$s[l:r]$中每个字母的数量进行加速，接着考虑如果我们已知了$s[l:r]$中每个字母出现次数的情况下，如何判断是否最多修改$k$个字符可以使其重排为回文串。首先，将每个字母左右放，那么剩余没地方放的字符即为出现了奇数次的字符，那些字符就必须得用修改次数了。显然那些字符种类数除以$2$之后如果小于等于$k$，即是可以，否则不可以。代码如下：

class Solution {
 public:
  vector<bool> canMakePaliQueries(string s, vector<vector<int>> &qs) {
    int n = s.size();
    vector<vector<int>> f(26, vector<int>(n + 1));
    for (int i = 0; i < n; i++) f[s[i] - 'a'][i + 1]++;

    for (auto &v : f)
      for (int i = 1; i <= n; i++) v[i] += v[i - 1];

    vector<bool> res(qs.size());
    for (int i = 0; i < qs.size(); i++) {
      auto &q = qs[i];
      int l = q[0], r = q[1], k = q[2], cnt = 0;
      for (auto &v : f)
        if ((v[r + 1] - v[l]) % 2) cnt++;

      res[i] = cnt / 2 <= k;
    }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

预处理时间复杂度$O(n)$，每次询问时间$O(1)$，空间$O(n)$。