# Can Make Palindrome from Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/can-make-palindrome-from-substring)
Canonical: https://scaleengineer.com/dsa/problems/can-make-palindrome-from-substring
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table, String
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
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 <= 105`
* `0 <= lefti <= righti < s.length`
* `0 <= ki <= s.length`
* `s` consists of lowercase English letters.

# Approaches
## Brute Force Iteration for Each Query
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize an empty list `answer`.
- For each query `[left, right, k]`:
  - Create a frequency map (an array of size 26).
  - Iterate from `left` to `right` and 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 `answer` list.
- Return the `answer` list.

## Prefix Parity Calculation using Bitmasks
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.
**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).
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- **Preprocessing:**
  - Create a prefix parity array `prefixParity` of size `s.length() + 1`.
  - Iterate through the string `s` to populate `prefixParity`. `prefixParity[i + 1] = prefixParity[i] ^ (1 << (s.charAt(i) - 'a'))`.
- **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 `substringMask` to get `oddCount`.
    - Check if `oddCount / 2 <= k`.
    - Add the boolean result to `answer`.
- Return `answer`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```