Can Make Palindrome from Substring - Video Solutions

Problem Overview: You receive a string s and multiple queries [l, r, k]. For each query, check whether the substring s[l..r] can be rearranged into a palindrome after replacing at most k characters. The key observation: a palindrome allows at most one character with odd frequency (more if you allow replacements).

Approach 1: Character Frequency Prefix Array (Time: O(n + q * 26), Space: O(n * 26))

Precompute prefix counts for every character in the alphabet. Create a 2D prefix array where prefix[i][c] stores how many times character c appears in the first i positions. For a query [l, r], compute the frequency of each character by subtracting two prefix rows. Iterate through the 26 counts and track how many characters have odd frequency. A substring can form a palindrome if oddCount / 2 ≤ k, since each replacement can fix two odd characters. This approach is straightforward and uses ideas from prefix sum and array preprocessing. It works well when the alphabet size is small and constant.

Approach 2: Bitmask for Odd Frequency Check (Time: O(n + q), Space: O(n))

Instead of storing full frequency counts, track only parity (odd/even). Maintain a prefix bitmask where each of the 26 bits represents whether the corresponding character has appeared an odd number of times so far. For each new character, toggle its bit using XOR. The mask for substring [l, r] is mask[r+1] ^ mask[l]. The number of set bits equals the count of characters with odd frequency. A palindrome allows at most one odd character, but with replacements you can fix pairs of odd counts. Compute oddCount = popcount(mask) and check if oddCount / 2 ≤ k. Bit operations make this extremely fast and memory efficient. This technique combines bit manipulation with prefix computation and avoids scanning all 26 characters for each query.

Recommended for interviews: The bitmask approach is usually what interviewers expect once you recognize the odd-frequency insight. The prefix frequency array still demonstrates solid understanding and is easier to derive during an interview. Showing the frequency idea first, then optimizing it with a bitmask, demonstrates strong problem-solving depth and familiarity with hash-based counting and prefix techniques.