# 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.

``````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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation