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 is true.
• 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 is false.
• 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 is false.
• 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 is true.
• 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 is true.

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]].

1. Start by building prefix-suffix array dp[], which is [0,2,6,4,20,16] for "abcda".
2. 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 in 16.
   • After calculating popcount(16), we get 1, which means there is 1 character with an odd frequency.
   • We compare 1/2 = 0 with k=0 value from the query, given that it is equal, we append True to the query results as we can form a palindrome.
3. 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 and 2/2 = 1 is not less or equal to k, we cannot form a palindrome from this substring, so we append False to the results.
4. 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 in dp[] 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 the ans else append False
• 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.