Can Make Palindrome from Substring

Can Make Palindrome from Substring

What is this problem about?

The Can Make Palindrome from Substring interview question involves a series of queries on a string. For each query [left, right, k], you need to determine if the substring from left to right can be transformed into a palindrome by rearranging characters and changing at most k characters. This Can Make Palindrome from Substring coding problem tests your understanding of palindromic properties and range queries.

Why is this asked in interviews?

Companies like Akuna Capital ask this to test efficiency in range-based queries. A naive solution (O(Q * N)) will be too slow. It requires using Prefix Sums or Bit Manipulation to count character frequencies across multiple ranges in O(1) or O(26) per query.

Algorithmic pattern used

This utilizes the Array, Hash Table, String, Bit Manipulation, Prefix Sum interview pattern.

• A substring can become a palindrome if the number of characters with odd frequencies is <= 2k + 1 (if length is odd) or <= 2k (if length is even).
• You can use a prefix sum array of bitmasks (where each bit represents the parity of a character 'a'-'z') to find the odd-frequency count of any substring in O(1).

Example explanation

s = "abcda", query = [1, 2, 0] (substring "bc").

• 'b' and 'c' both appear once (odd).
• 2 odd counts. k=0. We can't fix any. Palindrome needs <= 1 odd count (since length 2). Result: False. If query = [0, 3, 1] (substring "abcd"):
• 'a', 'b', 'c', 'd' all odd (4 odds).
• With k=1, we can change one char (e.g., 'd' to 'a'). Odds become 2.
• Still not a palindrome. If k=2, it would work.

Common mistakes candidates make

• Actually rearranging the string: Trying to build the palindrome, which is not required. Only the count of characters with odd frequencies matters.
• Linear Scan: Re-counting characters for every query instead of using prefix sums.
• Bitwise logic errors: Not correctly applying XOR to the bitmask to toggle character presence.

Interview preparation tip

Whenever you see "multiple queries on a substring" involving "counts" or "frequencies," think of Prefix Sums. If you only care about parity (even/odd), a Bitmask prefix sum is even more efficient.