Leetcode 1177: Can Make Palindrome from Substring
You are given a string
s and an array of queries queries, where queries[i] = [lefti, righti, ki]. For each query, you can rearrange the substring s[lefti...righti] and replace up to ki characters in it with any lowercase English letters. Determine whether it is possible to form a palindrome from the resulting substring. Return an array of booleans answer where answer[i] is true if it is possible to form a palindrome for the i-th query, otherwise false.Problem
Approach
Steps
Complexity
Input: The function receives a string `s` and an array `queries` as input.
Example: Input: s = 'abcbcba', queries = [[0, 6, 2], [1, 4, 1], [0, 2, 0], [3, 5, 1]]
Constraints:
• 1 <= s.length, queries.length <= 10^5
• 0 <= lefti <= righti < s.length
• 0 <= ki <= s.length
• s consists of lowercase English letters.
Output: The function returns a list of booleans indicating the result for each query.
Example: Output: [true, true, false, true]
Constraints:
• The output list must be of the same length as the input `queries`.
Goal: Check whether the substring defined by `lefti` and `righti` in each query can be rearranged and modified with up to `ki` character replacements to form a palindrome.
Steps:
• Calculate prefix bit masks to track character frequencies for the entire string.
• For each query, compute the XOR of prefix masks for the specified range to determine the odd-frequency characters.
• Count the number of odd-frequency characters and check if they can be adjusted to form a palindrome using up to `ki` replacements.
Goal: Ensure efficient handling of large inputs and fast computation for queries.
Steps:
• The solution should work in O(n + q) time, where `n` is the length of `s` and `q` is the number of queries.
• Minimize space usage by using prefix masks to represent character frequencies.
Assumptions:
• Each query operates independently without altering the input string `s`.
• Only lowercase English letters (26 characters) are considered.
• Input: Input: s = 'aabbcc', queries = [[0, 5, 1], [0, 3, 0], [2, 4, 2]]
• Explanation: Query 0: Substring 'aabbcc' can be rearranged to 'abcba' with 1 replacement. Query 1: Substring 'aabb' cannot be a palindrome without replacements. Query 2: Substring 'bbc' can be rearranged to 'cbc' with 2 replacements.
Approach: Use bit manipulation with prefix masks to efficiently compute the odd-frequency characters in each query range.
Observations:
• A string can be rearranged into a palindrome if at most one character has an odd frequency.
• Efficient range queries can be handled using prefix bit masks to store character frequency states.
• Track odd/even counts for characters using XOR.
• Check the number of odd counts and compare with the allowed replacements `ki`.
Steps:
• Build a prefix bit mask array for the string.
• For each query, calculate the XOR of masks for the range [lefti, righti].
• Count the number of set bits in the XOR result to find odd-frequency characters.
• Check if half the odd characters are less than or equal to `ki`.
• Append `true` or `false` to the results based on the above condition.
Empty Inputs:
• Empty string or empty queries array.
Large Inputs:
• Maximum possible length of `s` and number of queries.
Special Values:
• All characters in the substring are the same.
• Substring contains alternating characters.
Constraints:
• Ensure correct handling of indices and boundary conditions.
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& q) {
vector<bool> ans;
vector<int> pt(1,0);
int mask = 0;
for(int i = 0; i < s.length(); i++) {
pt.push_back(mask ^= 1 << (s[i] - 'a'));
}
for(int i = 0; i < q.size(); i++) {
auto &v = q[i];
int cnt = __builtin_popcount(pt[v[1]+1] ^ pt[v[0]]);
ans.push_back(cnt/2 <= v[2]);
}
return ans;
}
1 : Function Definition
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& q) {
Define the function `canMakePaliQueries` that takes a string `s` and a 2D vector of queries `q`. It returns a vector of booleans indicating whether the given substring can be rearranged into a palindrome with at most `k` modifications.
2 : Variable Initialization
vector<bool> ans;
Initialize the vector `ans` to store the results for each query.
3 : Variable Initialization
vector<int> pt(1,0);
Initialize a vector `pt` to store prefix XOR values, starting with 0.
4 : Variable Initialization
int mask = 0;
Initialize `mask` to 0. This variable will be used to track the state of characters in the string.
5 : Loop
for(int i = 0; i < s.length(); i++) {
Loop through each character in the string `s`.
6 : Bitwise Operation
pt.push_back(mask ^= 1 << (s[i] - 'a'));
Use bitwise operations to update `mask` for the current character and store the result in `pt`.
7 : Loop
for(int i = 0; i < q.size(); i++) {
Loop through each query in `q`.
8 : Variable Initialization
auto &v = q[i];
Get the current query from the list `q`.
9 : Bitwise Operation
int cnt = __builtin_popcount(pt[v[1]+1] ^ pt[v[0]]);
Calculate the number of different bits (i.e., characters) between the prefix sums at positions `v[0]` and `v[1]`.
10 : Vector Operation
ans.push_back(cnt/2 <= v[2]);
Push the result of the query (whether the count of different bits divided by 2 is less than or equal to `v[2]`) to the `ans` vector.
11 : Return Statement
return ans;
Return the vector `ans` containing the results of all queries.
Best Case: O(n + q)
Average Case: O(n + q)
Worst Case: O(n + q)
Description: Precomputing prefix masks takes O(n), and each query is processed in O(1).
Best Case: O(n)
Worst Case: O(n)
Description: Space is used for the prefix mask array and temporary variables.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus