1177. Can Make Palindrome from Substring

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation