Given a string s and an array of queries queries, where each query is represented as [left, right, k], your task is to determine for each query whether the substring s[left:right+1] can be transformed into a palindrome by changing at most k characters.
True) or not (False).s consists only of lowercase English letters.
At first glance, it seems we need to check for each substring if it can be rearranged (with changes) into a palindrome, considering the allowed number of modifications k. The naive approach is to, for each query, extract the substring, count letter frequencies, and check how many changes are needed. However, this would be slow for large numbers of queries because substring extraction and frequency counting are both costly.
To optimize, we notice that for a substring to be a palindrome, at most one character can have an odd count (for odd-length substrings), and all must be even for even-length substrings. If there are more than one odd-count characters, we must change some of them. The minimum number of changes needed is half the number of odd-count characters (since we can pair them up).
To efficiently compute character counts for any substring, we can use prefix sums (or prefix bitmasks) to preprocess the string, enabling O(1) queries for character parity.
i stores a bitmask representing the parity (even/odd) of character counts up to index i in s.[left, right, k], compute the parity mask for the substring by XOR-ing the prefix masks at right+1 and left.odd_count // 2, because each change can fix two odd-count characters by pairing them.odd_count // 2 ≤ k, the substring can be converted into a palindrome with at most k changes.
Suppose s = "abcda" and queries = [[0,4,1], [1,2,0]].
s (to build prefix mask).The key insight is that the number of character pairs with odd counts determines the minimum changes needed to form a palindrome. By using prefix bitmasks, we can answer each query in constant time after a linear-time preprocessing step. This approach is both elegant and efficient, leveraging bitwise operations for fast substring analysis, and avoids redundant computation by precomputing parity information.
class Solution:
def canMakePaliQueries(self, s, queries):
n = len(s)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] ^ (1 << (ord(s[i]) - ord('a')))
res = []
for left, right, k in queries:
mask = prefix[right+1] ^ prefix[left]
odd_count = bin(mask).count('1')
res.append((odd_count // 2) <= k)
return res
class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int n = s.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i+1] = prefix[i] ^ (1 << (s[i] - 'a'));
}
vector<bool> res;
for (auto& q : queries) {
int left = q[0], right = q[1], k = q[2];
int mask = prefix[right+1] ^ prefix[left];
int odd_count = __builtin_popcount(mask);
res.push_back((odd_count / 2) <= k);
}
return res;
}
};
class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int n = s.length();
int[] prefix = new int[n + 1];
for (int i = 0; i < n; ++i) {
prefix[i+1] = prefix[i] ^ (1 << (s.charAt(i) - 'a'));
}
List<Boolean> res = new ArrayList<>();
for (int[] q : queries) {
int left = q[0], right = q[1], k = q[2];
int mask = prefix[right+1] ^ prefix[left];
int odd_count = Integer.bitCount(mask);
res.add((odd_count / 2) <= k);
}
return res;
}
}
var canMakePaliQueries = function(s, queries) {
const n = s.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
prefix[i+1] = prefix[i] ^ (1 << (s.charCodeAt(i) - 97));
}
const res = [];
for (const [left, right, k] of queries) {
const mask = prefix[right+1] ^ prefix[left];
let odd_count = 0;
let m = mask;
while (m) {
odd_count += m & 1;
m >>= 1;
}
res.push(Math.floor(odd_count / 2) <= k);
}
return res;
};