Can make palindrome from substring

Array Hash Table String Bit Manipulation Prefix Sum

41.3% acceptance

Feb 25, 2026

875

281

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_make_pali_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<bool> {
    let n = s.len();
    // prefix XOR of character bitmasks
    let mut prefix = vec![0u32; n + 1];
    for (i, c) in s.bytes().enumerate() {
      prefix[i + 1] = prefix[i] ^ (1 << (c - b'a'));
    }
    queries.iter().map(|q| {
      let (l, r, k) = (q[0] as usize, q[1] as usize, q[2]);
      let xor = prefix[r + 1] ^ prefix[l];
      let odd_count = xor.count_ones() as i32;
      // Can make palindrome if odd_count/2 <= k
      odd_count / 2 <= k
    }).collect()
  }
}