You are given a string s and array queries where queries[i] = [lefti, righti, ki]. We may rearrange the substring s[lefti...righti] for each query and then choose up to ki 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 a boolean array answer where answer[i] is the result of the ith query queries[i].
Note that each letter is counted individually for replacement, so if, for example s[lefti...righti] = "aaa", and ki = 2, we can only replace two of the letters. Also, note that no query modifies the initial string s.
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.
Example 2:
Input: s = "lyb", queries = [[0,1,0],[2,2,1]] Output: [false,true]
Constraints:
1 <= s.length, queries.length <= 1050 <= lefti <= righti < s.length0 <= ki <= s.lengthsconsists of lowercase English letters.
class Solution:
def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
n = len(s)
ss = [[0] * 26 for _ in range(n + 1)]
for i, c in enumerate(s, 1):
ss[i] = ss[i - 1][:]
ss[i][ord(c) - ord("a")] += 1
ans = []
for l, r, k in queries:
cnt = sum((ss[r + 1][j] - ss[l][j]) & 1 for j in range(26))
ans.append(cnt // 2 <= k)
return ansclass Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int n = s.length();
int[][] ss = new int[n + 1][26];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j) {
ss[i][j] = ss[i - 1][j];
}
ss[i][s.charAt(i - 1) - 'a']++;
}
List<Boolean> ans = new ArrayList<>();
for (var q : queries) {
int l = q[0], r = q[1], k = q[2];
int x = 0;
for (int j = 0; j < 26; ++j) {
x += (ss[r + 1][j] - ss[l][j]) & 1;
}
ans.add(x / 2 <= k);
}
return ans;
}
}class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int n = s.size();
int ss[n + 1][26];
memset(ss, 0, sizeof(ss));
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j) {
ss[i][j] = ss[i - 1][j];
}
ss[i][s[i - 1] - 'a']++;
}
vector<bool> ans;
for (auto& q : queries) {
int l = q[0], r = q[1], k = q[2];
int x = 0;
for (int j = 0; j < 26; ++j) {
x += (ss[r + 1][j] - ss[l][j]) & 1;
}
ans.emplace_back(x / 2 <= k);
}
return ans;
}
};func canMakePaliQueries(s string, queries [][]int) (ans []bool) {
n := len(s)
ss := make([][26]int, n+1)
for i := 1; i <= n; i++ {
for j := 0; j < 26; j++ {
ss[i][j] = ss[i-1][j]
}
ss[i][s[i-1]-'a']++
}
for _, q := range queries {
l, r, k := q[0], q[1], q[2]
x := 0
for j := 0; j < 26; j++ {
x += (ss[r+1][j] - ss[l][j]) & 1
}
ans = append(ans, x/2 <= k)
}
return
}function canMakePaliQueries(s: string, queries: number[][]): boolean[] {
const n = s.length;
const ss: number[][] = Array(n + 1)
.fill(0)
.map(() => Array(26).fill(0));
for (let i = 1; i <= n; ++i) {
ss[i] = ss[i - 1].slice();
++ss[i][s.charCodeAt(i - 1) - 97];
}
const ans: boolean[] = [];
for (const [l, r, k] of queries) {
let x = 0;
for (let j = 0; j < 26; ++j) {
x += (ss[r + 1][j] - ss[l][j]) & 1;
}
ans.push(x >> 1 <= k);
}
return ans;
}