Can Make Palindrome from Substring solution and explanation
8 more videos on this problem
5175 Can Make Palindrome from SubstringKelvin Chandra · 12:00 · 2K views
1177. Can Make Palindrome from Substring | Leetcode Mediumcode Explainer · 11:14 · 2K views
Leetcode--1177 can make palindrome from substring (Hashmap)You Wu · 22:06 · 1K views
1177. Can Make Palindrome from Substring (Leetcode Medium)Programming Live with Larry · 10:13 · 518 views
米开：LeetCode 1177. Can Make Palindrome from SubstringM.C米开朗基罗 · 3:54 · 513 views
Leetcode 1177. Can Make Palindrome from Substring (prefix sum)LetsCode · 18:47 · 419 views
Can Make Palindrome from Substring, Medium, LeetCode 1177H William Polenz · 20:57 · 166 views
No Sound Leetcode 1177: Can Make Palindrome from SubstringExtremeProgrammer · 1:29 · 22 views
LeetCode 1177: Can Make Palindrome from SubstringAlitaCode · 30:32 · 9 views
The 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 <= 1050 <= lefti <= righti < s.length0 <= ki <= s.lengthsconsists of lowercase English letters.
Approach overview
Problem Overview: You receive a string s and multiple queries [l, r, k]. For each query, check whether the substring s[l..r] can be rearranged into a palindrome after replacing at most k characters. The key observation: a palindrome allows at most one character with odd frequency (more if you allow replacements).
Approach 1: Character Frequency Prefix Array (Time: O(n + q * 26), Space: O(n * 26))
Precompute prefix counts for every character in the alphabet. Create a 2D prefix array where prefix[i][c] stores how many times character c appears in the first i positions. For a query [l, r], compute the frequency of each character by subtracting two prefix rows. Iterate through the 26 counts and track how many characters have odd frequency. A substring can form a palindrome if oddCount / 2 ≤ k, since each replacement can fix two odd characters. This approach is straightforward and uses ideas from prefix sum and array preprocessing. It works well when the alphabet size is small and constant.
Approach 2: Bitmask for Odd Frequency Check (Time: O(n + q), Space: O(n))
Instead of storing full frequency counts, track only parity (odd/even). Maintain a prefix bitmask where each of the 26 bits represents whether the corresponding character has appeared an odd number of times so far. For each new character, toggle its bit using XOR. The mask for substring [l, r] is mask[r+1] ^ mask[l]. The number of set bits equals the count of characters with odd frequency. A palindrome allows at most one odd character, but with replacements you can fix pairs of odd counts. Compute oddCount = popcount(mask) and check if oddCount / 2 ≤ k. Bit operations make this extremely fast and memory efficient. This technique combines bit manipulation with prefix computation and avoids scanning all 26 characters for each query.
Recommended for interviews: The bitmask approach is usually what interviewers expect once you recognize the odd-frequency insight. The prefix frequency array still demonstrates solid understanding and is easier to derive during an interview. Showing the frequency idea first, then optimizing it with a bitmask, demonstrates strong problem-solving depth and familiarity with hash-based counting and prefix techniques.
Approach 1: Approach 1: Character Frequency Array
In this approach, we will use a frequency array to count the occurrences of each character in the substring. We can determine if a substring can be rearranged into a palindrome by observing the count of characters with odd frequencies as a palindrome allows at most one character with an odd frequency. We will iterate through each query, calculate the character frequencies for the specified substring, and count how many characters have an odd frequency. If the number of odd-frequency characters is less than or equal to 2 * k + 1 (since each replacement can fix two odd frequencies), the substring can potentially be rearranged into a palindrome.
from typing import List
class Solution:
def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
n = len(s)
prefix = [[0] * (n + 1) for _ in range(26)]
for i, char in enumerate(s):
for j in range(26):
prefix[j][i + 1] = prefix[j][i]
prefix[ord(char) - ord('a')][i + 1] += 1
results = []
for left, right, k in queries:
odd_count = 0
for j in range(26):
if (prefix[j][right + 1] - prefix[j][left]) % 2 != 0:
odd_count += 1
results.append(odd_count // 2 <= k)
return results
import java.util.List;
import java.util.ArrayList;
public class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int n = s.length();
int[][] prefix = new int[26][n + 1];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
prefix[j][i + 1] = prefix[j][i];
}
prefix[s.charAt(i) - 'a'][i + 1]++;
}
List<Boolean> results = new ArrayList<>();
for (int[] query : queries) {
int left = query[0], right = query[1], k = query[2];
int oddCount = 0;
for (int j = 0; j < 26; j++) {
int freq = prefix[j][right + 1] - prefix[j][left];
if (freq % 2 != 0) oddCount++;
}
results.add(oddCount / 2 <= k);
}
return results;
}
}
#include <vector>
#include <string>
using namespace std;
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int n = s.size();
vector<vector<int>> prefix(26, vector<int>(n + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
prefix[j][i + 1] = prefix[j][i];
}
prefix[s[i] - 'a'][i + 1]++;
}
vector<bool> results;
for (auto& query : queries) {
int left = query[0], right = query[1], k = query[2];
int oddCount = 0;
for (int j = 0; j < 26; ++j) {
int freq = prefix[j][right + 1] - prefix[j][left];
if (freq % 2 != 0) oddCount++;
}
results.push_back(oddCount / 2 <= k);
}
return results;
}
var canMakePaliQueries = function(s, queries) {
let n = s.length;
let prefix = Array.from({length: 26}, () => Array(n + 1).fill(0));
for (let i = 0; i < n; ++i) {
for (let j = 0; j < 26; ++j) {
prefix[j][i + 1] = prefix[j][i];
}
prefix[s.charCodeAt(i) - 97][i + 1]++;
}
let results = [];
for (let [left, right, k] of queries) {
let oddCount = 0;
for (let j = 0; j < 26; ++j) {
let freq = prefix[j][right + 1] - prefix[j][left];
if (freq % 2 !== 0) oddCount++;
}
results.push(Math.floor(oddCount / 2) <= k);
}
return results;
};
#include <stdbool.h>
#include <string.h>
bool* canMakePaliQueries(char * s, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
int n = strlen(s);
int prefix[26][n+1];
memset(prefix, 0, sizeof(prefix));
for (int i = 0; i < n; i++) {
for (int j = 0; j < 26; j++) {
prefix[j][i+1] = prefix[j][i];
}
prefix[s[i] - 'a'][i+1]++;
}
*returnSize = queriesSize;
bool* res = (bool*)malloc(queriesSize * sizeof(bool));
for (int i = 0; i < queriesSize; i++) {
int left = queries[i][0], right = queries[i][1], k = queries[i][2];
int oddCount = 0;
for (int j = 0; j < 26; j++) {
int freq = prefix[j][right+1] - prefix[j][left];
if (freq % 2 != 0) oddCount++;
}
res[i] = (oddCount / 2 <= k);
}
return res;
}
using System;
using System.Collections.Generic;
public class Solution {
public IList<bool> CanMakePaliQueries(string s, int[][] queries) {
int n = s.Length;
int[,] prefix = new int[26, n + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 26; j++) {
prefix[j, i + 1] = prefix[j, i];
}
prefix[s[i] - 'a', i + 1]++;
}
List<bool> results = new List<bool>();
foreach (int[] query in queries) {
int left = query[0], right = query[1], k = query[2];
int oddCount = 0;
for (int j = 0; j < 26; j++) {
int freq = prefix[j, right + 1] - prefix[j, left];
if (freq % 2 != 0) oddCount++;
}
results.Add(oddCount / 2 <= k);
}
return results;
}
}This Python solution applies the same methodology as previous language implementations, utilizing a prefix frequency matrix for all characters to streamline substring checks for each query. The count of odd character occurrences informs the determination of whether the desired palindrome can be established given k allowances for replacements.
Time Complexity: O(n + q * 26), linked to the number of character analysis.
Space Complexity: O(26 * n), for the storage of character occurrences within prefix array.
Approach 2: Approach 2: Bitmask for Odd Frequency Check
This approach involves using a bitmask to efficiently track which characters have an odd frequency across a range in the string. A bitmask allows us to toggle bits representing the state of a character's frequency parity (even/odd). For each query, the combined bitmask of characters in the range [left, right] is analyzed to determine how many bits are set to 1, reflecting odd character counts. This count, halved, represents the number of changes necessary to potentially convert the substring into a palindrome. If this count is within the allowed k changes, the query is satisfied.
from typing import List
class Solution:
def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
n = len(s)
prefix_masks = [0] * (n + 1)
for i in range(1, n + 1):
prefix_masks[i] = prefix_masks[i - 1] ^ (1 << (ord(s[i - 1]) - ord('a')))
results = []
for left, right, k in queries:
odd_count = bin(prefix_masks[right + 1] ^ prefix_masks[left]).count('1')
results.append(odd_count // 2 <= k)
return results
import java.util.List;
import java.util.ArrayList;
public class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int n = s.length();
int[] prefixMasks = new int[n + 1];
for (int i = 1; i <= n; ++i) {
prefixMasks[i] = prefixMasks[i - 1] ^ (1 << (s.charAt(i - 1) - 'a'));
}
List<Boolean> results = new ArrayList<>();
for (int[] query : queries) {
int left = query[0], right = query[1], k = query[2];
int oddCount = Integer.bitCount(prefixMasks[right + 1] ^ prefixMasks[left]);
results.add(oddCount / 2 <= k);
}
return results;
}
}
#include <vector>
#include <string>
#define POPCOUNT(x) __builtin_popcount(x)
std::vector<bool> canMakePaliQueries(std::string s, std::vector<std::vector<int>>& queries) {
int n = s.size();
std::vector<int> prefixMasks(n + 1, 0);
for (int i = 1; i <= n; ++i) {
prefixMasks[i] = prefixMasks[i - 1] ^ (1 << (s[i - 1] - 'a'));
}
std::vector<bool> results;
for (auto& query : queries) {
int left = query[0], right = query[1], k = query[2];
int oddCount = POPCOUNT(prefixMasks[right + 1] ^ prefixMasks[left]);
results.push_back((oddCount / 2) <= k);
}
return results;
}
var canMakePaliQueries = function(s, queries) {
let n = s.length;
let prefixMasks = Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
prefixMasks[i] = prefixMasks[i - 1] ^ (1 << (s.charCodeAt(i - 1) - 97));
}
let results = [];
for (let [left, right, k] of queries) {
let oddCount = (prefixMasks[right + 1] ^ prefixMasks[left]).toString(2).split('1').length - 1;
results.push(Math.floor(oddCount / 2) <= k);
}
return results;
};
#include <stdbool.h>
#include <stdlib.h>
bool* canMakePaliQueries(char * s, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
int n = strlen(s);
int* prefixMasks = (int*)malloc((n + 1) * sizeof(int));
prefixMasks[0] = 0;
for (int i = 1; i <= n; ++i) {
prefixMasks[i] = prefixMasks[i-1] ^ (1 << (s[i-1] - 'a'));
}
*returnSize = queriesSize;
bool* results = (bool*)malloc(queriesSize * sizeof(bool));
for (int i = 0; i < queriesSize; ++i) {
int left = queries[i][0];
int right = queries[i][1];
int k = queries[i][2];
int oddCount = __builtin_popcount(prefixMasks[right + 1] ^ prefixMasks[left]);
results[i] = (oddCount / 2) <= k;
}
free(prefixMasks);
return results;
}
using System;
using System.Collections.Generic;
public class Solution {
public IList<bool> CanMakePaliQueries(string s, int[][] queries) {
int n = s.Length;
int[] prefixMasks = new int[n + 1];
for (int i = 1; i <= n; ++i) {
prefixMasks[i] = prefixMasks[i - 1] ^ (1 << (s[i - 1] - 'a'));
}
List<bool> results = new List<bool>();
foreach (var query in queries) {
int left = query[0], right = query[1], k = query[2];
int oddCount = CountSetBits(prefixMasks[right + 1] ^ prefixMasks[left]);
results.Add(oddCount / 2 <= k);
}
return results;
}
private int CountSetBits(int x) {
int count = 0;
while (x > 0) {
count += x & 1;
x >>= 1;
}
return count;
}
}Utilizing a bitmask array, the Python solution assigns parity tracking values to characters in s. By using XOR, an efficient retrieval mechanism of character states is established. Final assessments rely on the number of changed states, juxtaposed against k, to appraise query feasibility for palindrome transformation.
Time Complexity: O(n + q), intersected by prefix calculation and bit operations.
Space Complexity: O(n), contingent on prefix mask setup.
Approach 3: Prefix Sum
First, consider whether a substring can become a palindrome after at most k replacements. Obviously, we need to count the number of times each character appears in the substring, which can be implemented through prefix sum. For characters that appear an even number of times, we do not need to replace them. For characters that appear an odd number of times, we need to replace them. The number of replacements is \lfloor \frac{x}{2} \rfloor, where x is the number of characters that appear an odd number of times. If \lfloor \frac{x}{2} \rfloor leq k, then this substring can become a palindrome.
Therefore, we define a prefix sum array ss, where ss[i][j] represents the number of times character j appears in the first i characters of string s. Then for a substring s[l..r], we can get the number of times character j appears in the substring through ss[r + 1][j] - ss[l][j]. We traverse all queries. For each query [l, r, k], we count the number of characters x that appear an odd number of times in the substring s[l..r]. If \lfloor \frac{x}{2} \rfloor leq k, then this substring can become a palindrome.
The time complexity is O((n + m) times C), and the space complexity is O(n times C). Here, n and m are the lengths of the string s and the query array respectively; and C is the size of the character set. In this problem, the character set is lowercase English letters, so C = 26.
function canMakePaliQueries(s: string, queries: number[][]): boolean[] {
const n = s.length;
const ss: number[][] = Array(n + 1)
.fill(0)
.map(() => Array(26).fill(0));
for (let i = 1; i <= n; ++i) {
ss[i] = ss[i - 1].slice();
++ss[i][s.charCodeAt(i - 1) - 97];
}
const ans: boolean[] = [];
for (const [l, r, k] of queries) {
let x = 0;
for (let j = 0; j < 26; ++j) {
x += (ss[r + 1][j] - ss[l][j]) & 1;
}
ans.push(x >> 1 <= k);
}
return ans;
}func canMakePaliQueries(s string, queries [][]int) (ans []bool) {
n := len(s)
ss := make([][26]int, n+1)
for i := 1; i <= n; i++ {
for j := 0; j < 26; j++ {
ss[i][j] = ss[i-1][j]
}
ss[i][s[i-1]-'a']++
}
for _, q := range queries {
l, r, k := q[0], q[1], q[2]
x := 0
for j := 0; j < 26; j++ {
x += (ss[r+1][j] - ss[l][j]) & 1
}
ans = append(ans, x/2 <= k)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Character Frequency Array | Time Complexity: O(n + q * 26), linked to the number of character analysis. |
| Approach 2: Bitmask for Odd Frequency Check | Time Complexity: O(n + q), intersected by prefix calculation and bit operations. |
| Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency Prefix Array | O(n + q * 26) | O(n * 26) | When the alphabet size is small and you want a clear, easy-to-derive prefix counting solution |
| Bitmask Odd-Frequency Prefix | O(n + q) | O(n) | Best choice for interviews and large query counts; constant-time parity check using bit operations |
Frequently asked questions
Is Can Make Palindrome from Substring easy or hard?
This problem is rated Medium because the core palindrome insight is simple but the efficient solution requires prefix preprocessing and bit manipulation. Recognizing that only odd character counts matter is the key step that leads to the optimal O(n + q) solution.
Can Make Palindrome from Substring Python/Java solution
Python and Java implementations typically use the prefix bitmask approach. Maintain an integer mask, toggle bits with XOR for each character, and store prefix masks. For each query, XOR two masks and use a built-in bit count function to check whether the number of odd characters can be fixed with k replacements.
How to solve Can Make Palindrome from Substring in O(n)?
Build a prefix XOR bitmask where each bit tracks the odd/even frequency of a character. For query [l, r], compute mask = prefix[r+1] ^ prefix[l]. Count the number of set bits using popcount to determine how many characters have odd frequency. If oddCount / 2 ≤ k, the substring can be rearranged into a palindrome after at most k replacements.
What is the best approach for Can Make Palindrome from Substring?
The optimal approach uses a prefix bitmask to track odd/even frequency of characters. Each bit represents whether a character appears an odd number of times up to that index. For a query, XOR two prefix masks to get the substring parity and count set bits. If oddCount / 2 ≤ k, the substring can be converted to a palindrome. This runs in O(n + q) time and O(n) space.
Is Can Make Palindrome from Substring asked at Google/Amazon/Meta?
Palindrome and prefix-parity problems frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. Variations involving substring queries, bitmask parity checks, and prefix sums are common because they test optimization and data structure knowledge.
What data structure is used in Can Make Palindrome from Substring?
Two main structures are used: a prefix frequency array and a prefix bitmask. The prefix array stores cumulative character counts, while the bitmask compresses parity information into a single integer using bit manipulation. Both rely on prefix sum concepts for constant-time substring queries.
What is the time complexity of Can Make Palindrome from Substring?
Using the optimal bitmask prefix technique, preprocessing the string takes O(n) time and each query is answered in O(1). Total complexity becomes O(n + q). The simpler prefix frequency array method runs in O(n + q * 26) because it checks all characters for every query.