Can Make Palindrome from Substring: Prefix XOR for Character Parity

May 27, 20265 min read

leetcodeproblemmediumstringshash-mapbit-manipulation

LeetCode 1177, Can Make Palindrome from Substring, gives you a string s and a list of queries. Each query is a triple [left, right, k], and you need to determine whether the substring s[left..right] can be rearranged into a palindrome after replacing at most k characters.

A brute-force approach would count character frequencies for each query independently, but with up to 10^5 queries on a string of length 10^5, that is way too slow. The trick is to precompute a prefix XOR bitmask that lets you answer each query in O(1).

The key insight: parity is all that matters

A string can be rearranged into a palindrome when at most one character has an odd frequency. Every character with an even frequency can be split evenly between the two halves of the palindrome. At most one odd-frequency character can sit in the middle.

You do not need exact frequency counts. You only need to know which characters have odd frequency. That is a parity question, and parity is exactly what XOR tracks.

For substring "bcb", only 'c' has an odd frequency. With k=1 replacements available, we can form a palindrome. Prefix XOR lets us compute odd-frequency counts for any substring in O(1).

The approach: prefix XOR bitmask

Assign each of the 26 lowercase letters a bit position (a = bit 0, b = bit 1, and so on). As you scan through the string, maintain a running XOR bitmask. Each time you see a character, toggle its bit. If a bit is 1 in the bitmask, that character has appeared an odd number of times so far.

Build a prefix array where prefix[i] holds the XOR bitmask for the first i characters. To find which characters have odd frequency in the substring s[left..right], compute prefix[right + 1] ^ prefix[left]. The XOR cancels out characters that appeared an even number of times in both halves, leaving only the characters with odd parity in the substring.

Count the number of set bits in that result. That is the number of characters with odd frequency. Each replacement can fix two odd-frequency characters (you replace one instance of character A with character B, making both even). So the number of replacements you need is popcount // 2. If that value is at most k, the answer is true.

Practice the prefix XOR bitmask technique

Python solution

def canMakePaliQueries(s, queries):
    prefix = [0] * (len(s) + 1)
    for i, ch in enumerate(s):
        prefix[i + 1] = prefix[i] ^ (1 << (ord(ch) - ord('a')))

    result = []
    for left, right, k in queries:
        odd_mask = prefix[right + 1] ^ prefix[left]
        odd_count = bin(odd_mask).count('1')
        result.append(odd_count // 2 <= k)
    return result

Walkthrough: s = "abcba"

Let's trace through the algorithm with s = "abcba" and the query [1, 3, 1]. The substring is "bcb" and we can make 1 replacement.

Step 1: Build prefix XOR array for s = "abcba"

Each character toggles its corresponding bit. After processing each character, the bitmask tracks which characters have appeared an odd number of times so far.

Step 2: Answer a query with XOR

For query [left, right], XOR prefix[right+1] with prefix[left]. The result tells you which characters appear an odd number of times in the substring.

Step 3: Check against k

A string can be rearranged into a palindrome if at most one character has an odd count (for odd-length strings). Each replacement fixes two odd-count characters, so you need popcount / 2 replacements.

The XOR of prefix[4] and prefix[1] gives 100 in binary. That is 1 set bit, meaning 1 character (c) has odd frequency in the substring. We need 1 // 2 = 0 replacements, and 0 is at most k = 1, so the answer is true.

The prefix XOR trick works because XOR is its own inverse. XOR-ing a value twice cancels it out. When you XOR prefix[right+1] with prefix[left], every character that appears in both the prefix up to left and the prefix up to right+1 cancels, leaving only the parity of the substring itself.

Drill prefix XOR queries with spaced repetition

Complexity analysis

Metric	Value
Time	O(n + q), where n is the length of s and q is the number of queries
Space	O(n) for the prefix array

Building the prefix array takes O(n). Each query is answered in O(1) using a single XOR and a popcount. The popcount operates on a 26-bit integer, so it is constant time.

Building blocks

This problem decomposes into two reusable building blocks that CodeBricks drills independently:

Prefix XOR for substring parity

Instead of recomputing frequencies from scratch for each query, you precompute a running XOR. The XOR at any index encodes which characters have appeared an odd number of times up to that point. Subtracting (via XOR) two prefix values gives you the parity for the substring between them. This same technique applies to any problem where you need range queries on parity or toggling state.

Popcount for decision making

Once you have a bitmask of odd-frequency characters, popcount tells you how many there are. The formula popcount // 2 converts that into the minimum number of replacements needed. This connection between set-bit counting and palindrome feasibility comes up in several string problems.

# Core pattern: prefix XOR + popcount
prefix = [0] * (len(s) + 1)
for i, ch in enumerate(s):
    prefix[i + 1] = prefix[i] ^ (1 << (ord(ch) - ord('a')))

odd_mask = prefix[right + 1] ^ prefix[left]
replacements_needed = bin(odd_mask).count('1') // 2

Once you can fluently build a prefix XOR array and count set bits, this problem reduces to a one-line check per query.

Edge cases

Empty substring (left equals right). A single character is always a palindrome. The XOR bitmask will have exactly one set bit, and 1 // 2 = 0 replacements are needed. This works correctly regardless of k.

k is 0. When no replacements are allowed, the substring must already be rearrangeable into a palindrome. That means at most one character has an odd frequency. The check popcount // 2 being at most 0 handles this.

All characters the same. If the substring is something like "aaaa", the XOR bitmask is 0 (all even frequencies). popcount(0) = 0, so 0 // 2 = 0 replacements are needed. Always true.

Large k. When k is very large (for example, k equals the substring length), the answer is always true. You can replace every character if needed. The algorithm handles this naturally since popcount // 2 never exceeds 13 (at most 26 letters).

From understanding to recall

The prefix XOR approach is elegant once you see it, but recognizing that parity tracking via XOR solves "can rearrange to palindrome" queries is the real skill. In an interview, you need to jump from "palindrome rearrangement" to "character parity" to "XOR bitmask" quickly.

Spaced repetition builds that chain of associations. You write the prefix XOR loop from scratch today, then again in a few days, then a week later. Each repetition strengthens the link between "substring palindrome queries" and "prefix XOR with popcount." Eventually, the pattern surfaces the moment you read the problem statement.

Build prefix XOR recall with CodeBricks

Palindromic Substrings - Counts all palindromic substrings using expand-from-center. A different angle on palindromes that focuses on enumeration rather than parity queries.
Longest Palindromic Substring - Finds the single longest palindromic substring. Both problems deal with palindrome properties of substrings, but this one uses expansion while problem 1177 uses XOR.
XOR Cancellation Pattern - A deep dive into the XOR cancellation property that makes prefix XOR work. If the XOR trick in this problem feels magical, that post explains the mechanics.