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 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 629,130 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