Can Make Palindrome from Substring
MedPrompt
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.lengthsconsists of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly implements the logic for each query without any pre-computation. For every query, it iterates through the specified substring, counts the frequency of each character, and then determines if it can be made a palindrome with the given number of replacements.
Algorithm
- Initialize an empty list
answer. - For each query
[left, right, k]:- Create a frequency map (an array of size 26).
- Iterate from
lefttorightand populate the frequency map for the substring. - Count the number of characters with an odd frequency (
oddCount). - Check if
oddCount / 2 <= k. - Add the boolean result to the
answerlist.
- Return the
answerlist.
Walkthrough
The core idea to check if a string can be a palindrome is to count the character frequencies. A string can be rearranged into a palindrome if at most one character has an odd frequency.
To solve this problem, we need to find the minimum number of character replacements to satisfy this condition. If we have a set of characters with odd counts, say {'a', 'b', 'c', 'd'}, we can change 'b' to 'a' and 'd' to 'c'. This costs 2 replacements and resolves all odd counts. In general, if we have m characters with odd counts, we need m / 2 replacements.
The brute-force algorithm applies this logic to each query independently.
class Solution { public List<Boolean> canMakePaliQueries(String s, int[][] queries) { List<Boolean> result = new ArrayList<>(); for (int[] query : queries) { int left = query[0]; int right = query[1]; int k = query[2]; int[] counts = new int[26]; for (int i = left; i <= right; i++) { counts[s.charAt(i) - 'a']++; } int oddCount = 0; for (int count : counts) { if (count % 2 != 0) { oddCount++; } } result.add(oddCount / 2 <= k); } return result; }}Complexity
Time
O(Q * N), where `Q` is the number of queries and `N` is the length of the string `s`. For each query, we might iterate up to `N` characters.
Space
O(1) or O(A) where A is the alphabet size (26). We only use a constant-size frequency array for each query. The space for the result list is O(Q).
Trade-offs
Pros
Simple to understand and implement.
Follows the problem description directly.
Uses minimal extra space (besides the result list).
Cons
Highly inefficient due to redundant calculations for each query.
Will not pass the time limits for the given constraints, leading to a 'Time Limit Exceeded' error.
This approach optimizes the process by pre-calculating the character count parities for all prefixes of the string. By doing so, we can find the character parities for any substring in constant time. This avoids the need to re-iterate through the substring for each query.
Algorithm
- Preprocessing:
- Create a prefix parity array
prefixParityof sizes.length() + 1. - Iterate through the string
sto populateprefixParity.prefixParity[i + 1] = prefixParity[i] ^ (1 << (s.charAt(i) - 'a')).
- Create a prefix parity array
- Query Processing:
- Initialize an empty list
answer. - For each query
[left, right, k]:- Calculate the substring's parity mask:
substringMask = prefixParity[right + 1] ^ prefixParity[left]. - Count the number of set bits in
substringMaskto getoddCount. - Check if
oddCount / 2 <= k. - Add the boolean result to
answer.
- Calculate the substring's parity mask:
- Initialize an empty list
- Return
answer.
Walkthrough
The key observation is that we only care about whether a character's count is odd or even, not its exact count. The parity of counts can be efficiently tracked using a bitmask. A 26-bit integer can represent the parities for all lowercase English letters, where the i-th bit is 1 if the i-th letter has an odd count, and 0 otherwise.
We can compute a prefix parity array. Let prefixParity[i] be the bitmask representing the character count parities for the prefix s[0...i-1].
The parity mask for a substring s[left...right] can then be calculated in O(1) time by prefixParity[right + 1] ^ prefixParity[left]. The XOR operation cancels out the parities from the prefix s[0...left-1], leaving only the parities for the desired substring.
Once we have the substring's parity mask, the number of characters with odd counts is simply the number of set bits (1s) in this mask. This can be found efficiently using built-in functions like Integer.bitCount().
The condition to check remains (number of odd counts) / 2 <= k.
class Solution { public List<Boolean> canMakePaliQueries(String s, int[][] queries) { int n = s.length(); // prefixParity[i] stores the parity mask for the prefix s[0...i-1] int[] prefixParity = new int[n + 1]; for (int i = 0; i < n; i++) { prefixParity[i + 1] = prefixParity[i] ^ (1 << (s.charAt(i) - 'a')); } List<Boolean> result = new ArrayList<>(); for (int[] query : queries) { int left = query[0]; int right = query[1]; int k = query[2]; // Get the parity mask for the substring s[left...right] int substringMask = prefixParity[right + 1] ^ prefixParity[left]; // Count the number of characters with odd frequencies int oddCount = Integer.bitCount(substringMask); // The number of changes needed is half the number of characters with odd counts int changesNeeded = oddCount / 2; result.add(changesNeeded <= k); } return result; }}Complexity
Time
O(N + Q), where `N` is the length of `s` and `Q` is the number of queries. The preprocessing step takes `O(N)` time. Each query is then answered in `O(1)` time.
Space
O(N), where N is the length of the string `s`, to store the `prefixParity` array. The space for the result list is O(Q).
Trade-offs
Pros
Highly efficient, with linear time complexity.
Solves the problem within the time limits by answering each query in constant time after preprocessing.
Clever use of bit manipulation and prefix sums for an elegant solution.
Cons
Requires extra space proportional to the length of the string for the prefix parity array.
The logic involving bitmasks and XOR might be less intuitive than the brute-force approach for beginners.
Solutions
Solution
class Solution {public List<Boolean> canMakePaliQueries(String s, int[][] queries) { int n = s.length(); int[][] ss = new int[n + 1][26]; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 26; ++j) { ss[i][j] = ss[i - 1][j]; } ss[i][s.charAt(i - 1) - 'a']++; } List<Boolean> ans = new ArrayList<>(); for (var q : queries) { int l = q[0], r = q[1], k = q[2]; int x = 0; for (int j = 0; j < 26; ++j) { x += (ss[r + 1][j] - ss[l][j]) & 1; } ans.add(x / 2 <= k); } return ans; }}class Solution {public: vector<bool> canMakePaliQueries(string s, vector<vector<int>> &queries) { int n = s.size(); int ss[n + 1][26]; memset(ss, 0, sizeof(ss)); for (int i = 1; i <= n; ++i) { for (int j = 0; j < 26; ++j) { ss[i][j] = ss[i - 1][j]; } ss[i][s[i - 1] - 'a']++; } vector<bool> ans; for (auto &q : queries) { int l = q[0], r = q[1], k = q[2]; int x = 0; for (int j = 0; j < 26; ++j) { x += (ss[r + 1][j] - ss[l][j]) & 1; } ans.emplace_back(x / 2 <= k); } return ans; }};class Solution: def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]: n = len(s) ss = [[0] * 26 for _ in range(n + 1)] for i, c in enumerate(s, 1): ss[i] = ss[i - 1][:] ss[i][ord(c) - ord("a")] += 1 ans = [] for l, r, k in queries: cnt = sum((ss[r + 1][j] - ss[l][j]) & 1 for j in range(26)) ans . append(cnt // 2 <= k) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.