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.In #1177 Can Make Palindrome from Substring, each query asks whether a substring can be rearranged into a palindrome after performing at most k character replacements. The key observation is that a string can form a palindrome if at most one character has an odd frequency (for odd-length strings), while the rest must be even.
To answer multiple queries efficiently, precompute a prefix representation of character parity. Instead of storing full frequencies, maintain a bitmask where each bit represents whether the count of a character is odd or even up to a certain index. For any substring, XOR the prefix masks to determine which characters have odd counts.
The number of odd-frequency characters determines the minimum replacements needed. If half of those odd counts is less than or equal to k, the substring can be converted into a palindrome. This approach enables very fast query processing using bit manipulation and prefix preprocessing.
The preprocessing runs in linear time, and each query can be evaluated in constant time.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Bitmask with Bit Manipulation | O(n + q) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Since we can rearrange the substring, all we care about is the frequency of each character in that substring.
How to find the character frequencies efficiently ?
As a preprocess, calculate the accumulate frequency of all characters for all prefixes of the string.
How to check if a substring can be changed to a palindrome given its characters frequency ?
Count the number of odd frequencies, there can be at most one odd frequency in a palindrome.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem reflects common interview themes such as prefix sums, bit manipulation, and substring queries. Variants of this logic are frequently discussed in technical interviews at large tech companies.
A bitmask combined with a prefix array is the most efficient structure. Each bit represents whether a character count is odd or even. This allows constant-time substring parity checks using XOR operations.
The optimal approach uses a prefix bitmask to track the parity (odd or even) of character frequencies. For each query, XOR the prefix masks to determine which characters appear an odd number of times. If the number of odd counts divided by two is less than or equal to k, the substring can be rearranged into a palindrome.
A palindrome requires pairs of characters mirrored around the center. Characters with odd frequency can only appear in the center or must be fixed with replacements. By counting odd frequencies, we can determine the minimum number of changes needed.