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.
Example :
Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] Output: [true,false,false,true,true] Explanation: queries[0]: substring = "d", is palidrome. queries[1]: substring = "bc", is not palidrome. queries[2]: substring = "abcd", is not palidrome after replacing only 1 character. queries[3]: substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab". queries[4]: substring = "abcda", could be changed to "abcba" which is palidrome.
Example 2:
Input: s = "lyb", queries = [[0,1,0],[2,2,1]] Output: [false,true]
Constraints:
1 <= s.length, queries.length <= 1050 <= lefti <= righti < s.length0 <= ki <= s.lengths consists of lowercase English letters.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.
In this approach, we will use a frequency array to count the occurrences of each character in the substring. We can determine if a substring can be rearranged into a palindrome by observing the count of characters with odd frequencies as a palindrome allows at most one character with an odd frequency. We will iterate through each query, calculate the character frequencies for the specified substring, and count how many characters have an odd frequency. If the number of odd-frequency characters is less than or equal to 2 * k + 1 (since each replacement can fix two odd frequencies), the substring can potentially be rearranged into a palindrome.
We build a prefix frequency array for each character. For each query, we compute the character frequencies in the given range using the prefix array. We then count the number of characters with odd frequencies. A palindrome can only have one character with an odd frequency in the case of odd length, or all characters even for even length. Thus, we can decide based on the number of replacements available and needed.
Time Complexity: O(n + q * 26), where n is the length of the string and q is the number of queries.
Space Complexity: O(26 * n), to store the prefix character frequencies.
This approach involves using a bitmask to efficiently track which characters have an odd frequency across a range in the string. A bitmask allows us to toggle bits representing the state of a character's frequency parity (even/odd). For each query, the combined bitmask of characters in the range [left, right] is analyzed to determine how many bits are set to 1, reflecting odd character counts. This count, halved, represents the number of changes necessary to potentially convert the substring into a palindrome. If this count is within the allowed k changes, the query is satisfied.
This solution maintains an array of prefix bitmasks, where each bit in a bitmask indicates whether the corresponding character has an odd frequency up to that point in the string. In processing each query, the XOR of two bitmasks provides a bitmask representing character parity within the query bounds. The number of set bits in this result indicates how many characters have odd frequencies, which is then evaluated against the number of allowed changes k.
Time Complexity: O(n + q), where n is the length of the string and q is the number of queries. Finding the popcount of a bitmask takes constant time.
Space Complexity: O(n), needed for storing the prefix bitmasks.
| Approach | Complexity |
|---|---|
| Approach 1: Character Frequency Array | Time Complexity: O(n + q * 26), where n is the length of the string and q is the number of queries. |
| Approach 2: Bitmask for Odd Frequency Check | Time Complexity: O(n + q), where n is the length of the string and q is the number of queries. Finding the popcount of a bitmask takes constant time. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency Prefix Array | O(n + q * 26) | O(n * 26) | When the alphabet size is small and you want a clear, easy-to-derive prefix counting solution |
| Bitmask Odd-Frequency Prefix | O(n + q) | O(n) | Best choice for interviews and large query counts; constant-time parity check using bit operations |
5175 Can Make Palindrome from Substring • Kelvin Chandra • 2,755 views views
Watch 9 more video solutions →Practice Can Make Palindrome from Substring with our built-in code editor and test cases.
Practice on FleetCode