Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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:

1
2

Input: s = "lyb", queries = [[0,1,0],[2,2,1]]
Output: [false,true]

Solution

Method 1 – Prefix XOR Frequency (Bitmask)

Intuition

To check if a substring can be rearranged into a palindrome with at most k replacements, we only need to know the parity (odd/even) of each character’s frequency. If at most k characters have odd frequency (or, more precisely, if we can fix all odd counts with k replacements), the substring can be made a palindrome. We can use prefix XOR bitmasks to efficiently answer each query in O(1) time after O(n) preprocessing.

Approach

  1. Precompute a prefix XOR array where each bit represents the parity of a character’s count up to that index.
  2. For each query, XOR the prefix values at right+1 and left to get the parity mask for the substring.
  3. Count the number of set bits (odd counts) in the mask. The minimum replacements needed is oddCount // 2.
  4. If oddCount // 2 <= k, the answer is true; otherwise, false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& q) {
        int n = s.size();
        vector<int> pre(n+1);
        for (int i = 0; i < n; ++i)
            pre[i+1] = pre[i] ^ (1 << (s[i] - 'a'));
        vector<bool> ans;
        for (auto& v : q) {
            int mask = pre[v[1]+1] ^ pre[v[0]];
            int odd = __builtin_popcount(mask);
            ans.push_back(odd/2 <= v[2]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func canMakePaliQueries(s string, q [][]int) []bool {
    n := len(s)
    pre := make([]int, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] ^ (1 << (s[i]-'a'))
    }
    ans := make([]bool, len(q))
    for i, v := range q {
        mask := pre[v[1]+1] ^ pre[v[0]]
        odd := 0
        for m := mask; m > 0; m >>= 1 {
            odd += m & 1
        }
        ans[i] = odd/2 <= v[2]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] q) {
        int n = s.length();
        int[] pre = new int[n+1];
        for (int i = 0; i < n; ++i)
            pre[i+1] = pre[i] ^ (1 << (s.charAt(i) - 'a'));
        List<Boolean> ans = new ArrayList<>();
        for (int[] v : q) {
            int mask = pre[v[1]+1] ^ pre[v[0]];
            int odd = Integer.bitCount(mask);
            ans.add(odd/2 <= v[2]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun canMakePaliQueries(s: String, q: Array<IntArray>): List<Boolean> {
        val n = s.length
        val pre = IntArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] xor (1 shl (s[i]-'a'))
        val ans = mutableListOf<Boolean>()
        for (v in q) {
            val mask = pre[v[1]+1] xor pre[v[0]]
            val odd = mask.countOneBits()
            ans.add(odd/2 <= v[2])
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def canMakePaliQueries(self, s: str, q: list[list[int]]) -> list[bool]:
        n = len(s)
        pre = [0]*(n+1)
        for i in range(n):
            pre[i+1] = pre[i] ^ (1 << (ord(s[i])-97))
        ans = []
        for l, r, k in q:
            mask = pre[r+1] ^ pre[l]
            odd = bin(mask).count('1')
            ans.append(odd//2 <= k)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn can_make_pali_queries(s: String, q: Vec<Vec<i32>>) -> Vec<bool> {
        let n = s.len();
        let s = s.as_bytes();
        let mut pre = vec![0; n+1];
        for i in 0..n {
            pre[i+1] = pre[i] ^ (1 << (s[i]-b'a'));
        }
        q.iter().map(|v| {
            let mask = pre[v[1] as usize + 1] ^ pre[v[0] as usize];
            mask.count_ones()/2 <= v[2] as u32
        }).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    canMakePaliQueries(s: string, q: number[][]): boolean[] {
        const n = s.length, pre = new Array(n+1).fill(0), ans = [];
        for (let i = 0; i < n; ++i)
            pre[i+1] = pre[i] ^ (1 << (s.charCodeAt(i)-97));
        for (const [l, r, k] of q) {
            const mask = pre[r+1] ^ pre[l];
            const odd = mask.toString(2).split('1').length-1;
            ans.push(Math.floor(odd/2) <= k);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + q), where n is the length of s and q is the number of queries. Preprocessing is O(n), each query is O(1).
  • 🧺 Space complexity: O(n), for the prefix array.