Leetcode 1177. Can Make Palindrome from Substring
Problem Explanation
Given a string s
and an array of queries, we need to determine if the substrings defined by the queries can be rearranged to form a palindrome, taking into account a limit on the number of characters that can be replaced. Each query is an array of three integers: the position of the starting character of the substring, the position of the last character of the substring, and the number of characters that can be replaced.
A palindrome is a word that can be read the same way forwards and backwards. To constitute a palindrome, a string must have an even number of each character (except one character, if the length of the string is odd).
For example, given the string "abcda"
and the queries [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
.
- For the first query, [3,3,0], the substring is
"d"
, which is already a palindrome. Thus, the answer for this query istrue
. - For the second query, [1,2,0], the substring is
"bc"
, which cannot be a palindrome because no letters can be replaced. Thus, the answer for this query isfalse
. - For the third query, [0,3,1], the substring is
"abcd"
, which is not a palindrome even after replacing 1 character. Thus, the answer for this query isfalse
. - For the fourth query, [0,3,2], the substring is
"abcd"
. By replacing 2 characters"c"
and"d"
with"a"
and"b"
respectively, we can get a palindrome"abba"
. Thus, the answer for this query istrue
. - For the last query, [0,4,1], the substring is
"abcda"
. We can replace"b"
with"a"
to get a palindrome"aca"
or replace "d" with "c" to get palindrome "abccba". Thus, the answer for this query istrue
.
The solution needs to return an array of boolean values, each representing whether the substrings of the queries can be a palindrome or not.
Solution Explanation
The solution uses bitwise operations to store and calculate the frequencies of characters in substrings. It creates a prefix-suffix array dp[]
storing XOR of characters from the start to current character of string s
.
Every time a query is made, it XOR's the appropriate values in the dp[]
to get the frequencies of characters in the required substring. PopCount (number of set bits) gives us how many characters have odd frequencies i.e how many characters cannot be paired.
We can get a palindrome from the substring by replacing "half of these unpaired characters".
Then, it checks if the number of unpaired characters divided by 2 is less or equal to the number of replacements k
allowed for the query. If it is, we can form a palindrome.
Example Walkthrough
Consider the string s = "abcda"
and the queries queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
.
- Start by building prefix-suffix array
dp[]
, which is[0,2,6,4,20,16]
for"abcda"
. - For the first query
[3,3,0]
,- the frequencies of characters in the substring is obtained by XOR
dp[3 + 1] & dp[3]
which results in16
. - After calculating popcount(16), we get
1
, which means there is 1 character with an odd frequency. - We compare
1/2 = 0
withk=0
value from the query, given that it is equal, we appendTrue
to the query results as we can form a palindrome.
- the frequencies of characters in the substring is obtained by XOR
- For the second query
[1,2,0]
,- the character frequencies in the substring are
dp[2 + 1] ^ dp[1] = 6
, - popcount(6) gives us
2
, which means there are 2 characters with odd frequency. - Since
k=0
and2/2 = 1
is not less or equal tok
, we cannot form a palindrome from this substring, so we appendFalse
to the results.
- the character frequencies in the substring are
- Repeat the process described above for all other queries.
Algorithm
- Initialize result as an empty array
ans
- Calculate prefix-xor of the string
s
and store indp[]
array - For each query in queries
- XOR the prefix-xor array from position [left] to [right] to get the frequencies.
- Calculate the number of characters with odd frequencies by performing popcount
- If the half of number of characters with odd frequencies is less than or equal to the number of changes allowed, append
True
to theans
else appendFalse
- Return the
ans
array
Python Solution
1 2python 3class Solution: 4 def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]: 5 res = [] 6 dp = [0] 7 for i in range(1, len(s)+1): 8 dp.append(dp[i-1] ^ (1 << (ord(s[i-1]) - 97))) 9 for left, right, k in queries: 10 res.append(bin(dp[right+1] ^ dp[left]).count('1') // 2 <= k) 11 return res
Java Solution
1
2java
3class Solution {
4 public List<Boolean> canMakePaliQueries(String s, List<int[]> queries) {
5 List<Boolean> res = new ArrayList<>();
6 int[] dp = new int[s.length() + 1];
7 for (int i = 1; i <= s.length(); i++)
8 dp[i] = dp[i - 1] ^ (1 << (s.charAt(i - 1) - 'a'));
9
10 for (int[] query : queries) {
11 int odds = Integer.bitCount(dp[query[1] + 1] ^ dp[query[0]]);
12 res.add(odds / 2 <= query[2]);
13 }
14 return res;
15 }
16}
JavaScript Solution
1
2javascript
3class Solution {
4 canMakePaliQueries(s, queries) {
5 let res = [];
6 let dp = [0];
7 for (let i = 1; i <= s.length; i++)
8 dp[i] = dp[i - 1] ^ (1 << (s.charCodeAt(i - 1) - 97));
9
10 for (let query of queries) {
11 let odds = (dp[query[1] + 1] ^ dp[query[0]]).toString(2).split('0').join('').length;
12 res.push(odds / 2 <= query[2]);
13 }
14 return res;
15 }
16}
C++ Solution
1
2c++
3class Solution {
4public:
5 vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
6 vector<bool> res;
7 vector<int> dp(s.length() + 1);
8 for (int i = 1; i <= s.length(); i++)
9 dp[i] = dp[i - 1] ^ (1 << (s[i - 1] - 'a'));
10
11 for (vector<int>& query : queries) {
12 int odds = __builtin_popcount(dp[query[1] + 1] ^ dp[query[0]]);
13 res.push_back(odds / 2 <= query[2]);
14 }
15 return res;
16 }
17};
C# Solution
1
2csharp
3public class Solution {
4 public IList<bool> CanMakePaliQueries(string s, int[][] queries) {
5 List<bool> res = new List<bool>();
6 int[] dp = new int[s.Length + 1];
7 for (int i = 1; i <= s.Length; i++)
8 dp[i] = dp[i - 1] ^ (1 << (s[i - 1] - 'a'));
9
10 foreach (int[] query in queries) {
11 int odds = PopCount(dp[query[1] + 1] ^ dp[query[0]]);
12 res.Add(odds / 2 <= query[2]);
13 }
14 return res;
15 }
16
17 private static int PopCount(int n) {
18 int count = 0;
19 while(n != 0) {
20 n &= (n - 1);
21 count++;
22 }
23 return count;
24 }
25}
Swift Solution
1 2swift 3class Solution { 4 func canMakePaliQueries(_ s: String, _ queries: [[Int]]) -> [Bool] { 5 var res = [Bool]() 6 var dp = Array(repeating: 0, count: s.count + 1) 7 let sArray = Array(s) 8 for i in 1...s.count { 9 dp[i] = dp[i-1] ^ (1 << (sArray[i-1].asciiValue! - 97)) 10 } 11 12 for query in queries { 13 let odds = popCount(x: dp[query[1] + 1] ^ dp[query[0]]) 14 res.append(odds / 2 <= query[2]) 15 } 16 return res 17 } 18 19 func popCount(x: Int) -> Int { 20 var count = 0, x = x 21 while x != 0 { 22 x &= x - 1 23 count += 1 24 } 25 return count 26 } 27}
In Swift, firstly we create a character array sArray
from string s
as Swift does not provide direct character access from strings. The ASCII value of each characters are found using asciiValue
property.
Ruby Solution
1 2ruby 3class Solution 4 def can_make_pali_queries(s, queries) 5 res = [] 6 dp = [0] 7 s.each_char.with_index(1) do |c, i| 8 dp[i] = dp[i - 1] ^ (1 << (c.ord - 97)) 9 end 10 queries.each do |query| 11 odds = pop_count(dp[query[1] + 1] ^ dp[query[0]]) 12 res << (odds / 2 <= query[2]) 13 end 14 res 15 end 16 17 def pop_count(n) 18 count = 0 19 while n != 0 20 n &= (n - 1) 21 count += 1 22 end 23 count 24 end 25end
In Ruby, we can iterate over each character of the string using each_char
method. The ASCII value of each characters can be found using ord
method.
Note that for C#, C++ and Python, there are built-in functions available to count the number of set bits (__builtin_popcount
in C++, Integer.bitCount
in Java and bin(n).count('1')
in Python).
For JavaScript, Swift and Ruby, we either count the number of '1's ourselves using loops or count '1' in binary representation of the XOR result.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.