## 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 : substring = "d", is palidrome.
queries : substring = "bc", is not palidrome.
queries : substring = "abcd", is not palidrome after replacing only 1 character.
queries : 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 : substring = "abcda", could be changed to "abcba" which is palidrome.
```

Constraints:

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

## Rust Solution

``````struct Solution;

impl Solution {
fn can_make_pali_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<bool> {
let n = s.len();
let mut prefix: Vec<u32> = vec![0; n + 1];
for (i, c) in s.char_indices() {
prefix[i + 1] = prefix[i] ^ (1 << (c as u32 - 'a' as u32));
}
let mut res = vec![];
for q in queries {
let left = q as usize;
let right = q as usize + 1;
let k = q as u32;
res.push(k * 2 >= (prefix[right] ^ prefix[left]).count_ones() - 1);
}
res
}
}

#[test]
fn test() {
let s = "abcda".to_string();
let queries = vec_vec_i32![[3, 3, 0], [1, 2, 0], [0, 3, 1], [0, 3, 2], [0, 4, 1]];
let res = vec![true, false, false, true, true];
assert_eq!(Solution::can_make_pali_queries(s, queries), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.