[LeetCode] 1177. Can Make Palindrome from Substring

[grandyang]

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters.  (Also, note that the initial string s is never modified by any query.)

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

Constraints:

• 1 <= s.length, queries.length <= 10^5
• 0 <= queries[i][0] <= queries[i][1] < s.length
• 0 <= queries[i][2] <= s.length
• s only contains lowercase English letters.

这道题给了一个只有小写字母的字符串s，让对s对子串进行查询。查询块包含三个信息，left，right 和k，其中 left 和 right 定义了子串的范围，k表示可以进行替换字母的个数。这里希望通过替换可以将子串变为回文串，关于回文串想必各位刷题老司机都不陌生吧，就是正读反读都一样，比如 noon，bob 等等。题目中还说了可以事先给子串进行排序，这个条件一加，整个性质就不一样了，若不能排序，那么要替换的字母可能就很多了，因为对应的位置上的字母要相同才行。而能排序之后，只要把相同的字母尽可能的排列到对应的位置上，就可以减少要替换的字母，比如 hunu，若不能重排列，则至少要替换两个字母才行，而能重排顺序的话，可以先变成 uhnu，再替换中间的任意一个字母就可以了。而仔细观察，需要替换的情况都是字母出现次数为奇数的情况，偶数的字母完全不用担心，所以只要统计出出现次数为奇数的字母的个数，其除以2就是要替换的次数。那可能有的童鞋会问了，万一是奇数怎么办，除以2除不尽怎么办，这是个好问题。若出现次数为奇数的字母的个数为奇数，则表明该子串的长度为奇数，而奇数回文串最中间的字母是不需要有对称位置的，所以自然可以少替换一个，所以除不尽的部分就自动舍去了，并不影响最终的结果。讲到这里，应该就不难做了，但博主最先写的解法超时 TLE 了，做法是取出每个要查询的子串，然后统计出现奇数次的字母个数，再除以2跟k比较。这种方法并不高效，可能会存在大量的重复计算。就比如求子数组之和一样，若对于每个给定的子数组，都遍历一遍求和，确实不高效，一般都是建立累加和数组来做。这里也可以借鉴类似的想法，不过这里是对每个子串都建立字母出现次数的映射，所以这里用一个二维数组，大小为 n+1 by 26，因为限定了只有小写字母。然后遍历字符串s进行更新，每次先将 cnt[i+1] 赋值为 cnt[i]，然后在对应的字母位置映射值自增1。累加好了之后，对于任意区间 [i, j] 的次数映射数组就可以通过 cnt[j+1] - cnt[i] 来表示，但数组之间不好直接做减法，可以再进一步访问每个字母来分别进行处理，快速得到每个字母的出现次数后除以2，将结果累加到 sum 中，就是出现奇数次字母的个数了，再除以2和k比较即可，参见代码如下：

class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        vector<bool> res;
        vector<vector<int>> cnt(s.size() + 1, vector<int>(26));
        for (int i = 0; i < s.size(); ++i) {
            cnt[i + 1] = cnt[i];
            ++cnt[i + 1][s[i] - 'a'];
        }
        for (auto &query : queries) {
            int sum = 0;
            for (int i = 0; i < 26; ++i) {
                sum += (cnt[query[1] + 1][i] - cnt[query[0]][i]) % 2;
            }
            res.push_back(sum / 2 <= query[2]);
        }
        return res;
    }
};

Github 同步地址:

#1177

参考资料：

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

https://leetcode.com/problems/can-make-palindrome-from-substring/discuss/372044/Short-and-fast-C%2B%2B-prefix-xor-solution-beats-100

https://leetcode.com/problems/can-make-palindrome-from-substring/discuss/371849/JavaPython-3-3-codes-each%3A-prefix-sum-boolean-and-xor-of-characters'-frequencies-then-compare

LeetCode All in One 题目讲解汇总(持续更新中...)