Can Make Palindrome from Substring

medium prefix sum parity palindrome

Problem

Given a string s and queries [left, right, k]. For each query, take the substring s[left..right]. You may rearrange its letters freely and may replace up to k of them with any letters. Return true if the substring can be turned into a palindrome. A palindrome can be formed when at most one character has an odd count, so each replacement can fix one odd-count character; the answer is (number of odd-count characters) / 2 ≤ k.

Inputs = "abcda", query = [0, 4, 1]

Outputtrue

Substring "abcda" has odd counts for b, c, d (3 odds). We need floor(3/2)=1 replacement, and k=1, so it works.

s (lowercase letters)

left

right

def can_make_pali_queries(s, queries):
    n = len(s)
    pre = [0] * (n + 1)
    for i, ch in enumerate(s):
        pre[i + 1] = pre[i] ^ (1 << (ord(ch) - 97))
    res = []
    for left, right, k in queries:
        mask = pre[right + 1] ^ pre[left]
        odds = bin(mask).count("1")
        res.append(odds // 2 <= k)
    return res

function canMakePaliQueries(s, queries) {
  const n = s.length;
  const pre = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    pre[i + 1] = pre[i] ^ (1 << (s.charCodeAt(i) - 97));
  }
  return queries.map(function ([left, right, k]) {
    let mask = pre[right + 1] ^ pre[left];
    let odds = 0;
    while (mask) { odds += mask & 1; mask >>= 1; }
    return Math.floor(odds / 2) <= k;
  });
}

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        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> res = new ArrayList<>();
        for (int[] q : queries) {
            int mask = pre[q[1] + 1] ^ pre[q[0]];
            int odds = Integer.bitCount(mask);
            res.add(odds / 2 <= q[2]);
        }
        return res;
    }
}

vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    int n = s.size();
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] ^ (1 << (s[i] - 'a'));
    }
    vector<bool> res;
    for (auto& q : queries) {
        int mask = pre[q[1] + 1] ^ pre[q[0]];
        int odds = __builtin_popcount(mask);
        res.push_back(odds / 2 <= q[2]);
    }
    return res;
}

Explanation

Since we can rearrange the substring freely, only the letter counts matter for forming a palindrome. A string can become a palindrome when at most one letter has an odd count, and each allowed replacement can fix one odd letter, so we need (number of odd counts) / 2 ≤ k.

The clever part is tracking only parity (odd vs even) of each letter using a 26-bit bitmask, and turning it into a prefix XOR. pre[i+1] is the XOR of all letter-bits up to index i; flipping a bit toggles that letter between odd and even.

For a query [left, right, k], the parity mask of just that substring is pre[right+1] ^ pre[left] — XORing cancels everything outside the range. The number of set bits in that mask (odds) is how many letters have odd counts, and we answer odds // 2 ≤ k.

Example: s = "abcda", query [0,4,1]. The substring "abcda" has odd counts for b, c, d (3 odds). We need 3 // 2 = 1 replacement, and k = 1, so the answer is true.

Building the prefix array is one pass, and each query is then answered in constant time, giving O(n + q) overall.

Time: O(n + q) Space: O(n)