1177. 构建回文串检测 (opens new window)

1.字典序前缀和

题目有两个要求：①子串是回文②判断当前子串时，子串可以进行重排。因为可以重排的缘故，对于子串的每一个字母来说，只要同时出现了两次(或者是偶数次)，那么就可以满足回文的性质，而不需要考虑这些字母出现的位置是否满足回文对称的性质。

难点就转化成如何在常数量级下，得到每一个子串字母出现的次数。此处做法是使用前缀和，【start,end】子串的字母出现次数就等于以end结尾的子串字母出现次数，减去以start-1结尾子串的字母出现次数。此处给出的题解用List<int[ 26]>容器维护当前时刻字母出现的次数，当然也可以使用二维数组。

💡一维数组对象clone()方法：返回一个当前数组的拷贝对象。

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Boolean> list=new ArrayList<>();
        List<int[]> dict=new ArrayList<>();
        int[] nums=new int[26];
        for(int i=0;i<s.length();i++){
            nums[s.charAt(i)-'a']+=1;
            dict.add(nums.clone());
        }
        for(int i=0;i<queries.length;i++){
            int start=queries[i][0],end=queries[i][1],k=queries[i][2],sum=0;
            int[] pre2=dict.get(end).clone();
            if(start!=0){
                int[] pre1=dict.get(start-1);
                for(int j=0;j<26;j++){
                    pre2[j]-=pre1[j];
                } 
            }
            for(int j=0;j<26;j++){
                sum+=pre2[j]%2;
            } 
            
            if(sum/2>k) list.add(false);
            else list.add(true);
        }
        return list;
    }
}