LC.P1177[构建回文串检测]

方法一：前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        int[][] sum = new int[n + 1][26];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 26; ++j) {
                sum[i][j] = sum[i - 1][j];
            }
            ++sum[i][s.charAt(i - 1) - 'a'];
        }
        List<Boolean> ans = new ArrayList<>();
        for (int[] query : queries) {
            int l = query[0], r = query[1], k = query[2];
            int x = 0;
            for (int j = 0; j < 26; ++j) {
                // 奇数+1，偶数+0
                x += (sum[r + 1][j] - sum[l][j]) & 1;
            }
            ans.add(x / 2 <= k);
        }
        return ans;
    }
}
  • 时间复杂度：$O((n + m) \times C)$，其中$C = 26$
  • 空间复杂度：$O(n \times C)$