Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given a 0-indexed string s having an even length n.
You are also given a 0-indexed 2D integer array, queries, where queries[i] = [ai, bi, ci, di].
For each query i, you are allowed to perform the following operations:
s[ai:bi], where 0 <= ai <= bi < n / 2.s[ci:di], where n / 2 <= ci <= di < n.For each query, your task is to determine whether it is possible to make s a palindrome by performing the operations.
Each query is answered independently of the others.
Return a 0-indexed array answer, where answer[i] == true if it is possible to make s a palindrome by performing operations specified by the ith query, and false otherwise.
s[x:y] represents the substring consisting of characters from the index x to index y in s, both inclusive.Example 1:
Input: s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]] Output: [true,true] Explanation: In this example, there are two queries: In the first query: - a0 = 1, b0 = 1, c0 = 3, d0 = 5. - So, you are allowed to rearrange s[1:1] => abcabc and s[3:5] => abcabc. - To make s a palindrome, s[3:5] can be rearranged to become => abccba. - Now, s is a palindrome. So, answer[0] = true. In the second query: - a1 = 0, b1 = 2, c1 = 5, d1 = 5. - So, you are allowed to rearrange s[0:2] => abcabc and s[5:5] => abcabc. - To make s a palindrome, s[0:2] can be rearranged to become => cbaabc. - Now, s is a palindrome. So, answer[1] = true.
Example 2:
Input: s = "abbcdecbba", queries = [[0,2,7,9]] Output: [false] Explanation: In this example, there is only one query. a0 = 0, b0 = 2, c0 = 7, d0 = 9. So, you are allowed to rearrange s[0:2] => abbcdecbba and s[7:9] => abbcdecbba. It is not possible to make s a palindrome by rearranging these substrings because s[3:6] is not a palindrome. So, answer[0] = false.
Example 3:
Input: s = "acbcab", queries = [[1,2,4,5]] Output: [true] Explanation: In this example, there is only one query. a0 = 1, b0 = 2, c0 = 4, d0 = 5. So, you are allowed to rearrange s[1:2] => acbcab and s[4:5] => acbcab. To make s a palindrome s[1:2] can be rearranged to become abccab. Then, s[4:5] can be rearranged to become abccba. Now, s is a palindrome. So, answer[0] = true.
Constraints:
2 <= n == s.length <= 1051 <= queries.length <= 105queries[i].length == 4ai == queries[i][0], bi == queries[i][1]ci == queries[i][2], di == queries[i][3]0 <= ai <= bi < n / 2n / 2 <= ci <= di < n n is even.s consists of only lowercase English letters.Problem summary: You are given a 0-indexed string s having an even length n. You are also given a 0-indexed 2D integer array, queries, where queries[i] = [ai, bi, ci, di]. For each query i, you are allowed to perform the following operations: Rearrange the characters within the substring s[ai:bi], where 0 <= ai <= bi < n / 2. Rearrange the characters within the substring s[ci:di], where n / 2 <= ci <= di < n. For each query, your task is to determine whether it is possible to make s a palindrome by performing the operations. Each query is answered independently of the others. Return a 0-indexed array answer, where answer[i] == true if it is possible to make s a palindrome by performing operations specified by the ith query, and false otherwise. A substring is a contiguous sequence of characters within a string. s[x:y] represents the substring consisting of characters from the index x to index y in s,
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"abcabc" [[1,1,3,5],[0,2,5,5]]
"abbcdecbba" [[0,2,7,9]]
"acbcab" [[1,2,4,5]]
longest-chunked-palindrome-decomposition)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2983: Palindrome Rearrangement Queries
class Solution {
public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
int n = s.length();
int m = n / 2;
String t = new StringBuilder(s.substring(m)).reverse().toString();
s = s.substring(0, m);
int[][] pre1 = new int[m + 1][0];
int[][] pre2 = new int[m + 1][0];
int[] diff = new int[m + 1];
pre1[0] = new int[26];
pre2[0] = new int[26];
for (int i = 1; i <= m; ++i) {
pre1[i] = pre1[i - 1].clone();
pre2[i] = pre2[i - 1].clone();
++pre1[i][s.charAt(i - 1) - 'a'];
++pre2[i][t.charAt(i - 1) - 'a'];
diff[i] = diff[i - 1] + (s.charAt(i - 1) == t.charAt(i - 1) ? 0 : 1);
}
boolean[] ans = new boolean[queries.length];
for (int i = 0; i < queries.length; ++i) {
int[] q = queries[i];
int a = q[0], b = q[1];
int c = n - 1 - q[3], d = n - 1 - q[2];
ans[i] = a <= c ? check(pre1, pre2, diff, a, b, c, d)
: check(pre2, pre1, diff, c, d, a, b);
}
return ans;
}
private boolean check(int[][] pre1, int[][] pre2, int[] diff, int a, int b, int c, int d) {
if (diff[a] > 0 || diff[diff.length - 1] - diff[Math.max(b, d) + 1] > 0) {
return false;
}
if (d <= b) {
return Arrays.equals(count(pre1, a, b), count(pre2, a, b));
}
if (b < c) {
return diff[c] - diff[b + 1] == 0 && Arrays.equals(count(pre1, a, b), count(pre2, a, b))
&& Arrays.equals(count(pre1, c, d), count(pre2, c, d));
}
int[] cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
int[] cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));
return cnt1 != null && cnt2 != null && Arrays.equals(cnt1, cnt2);
}
private int[] count(int[][] pre, int i, int j) {
int[] cnt = new int[26];
for (int k = 0; k < 26; ++k) {
cnt[k] = pre[j + 1][k] - pre[i][k];
}
return cnt;
}
private int[] sub(int[] cnt1, int[] cnt2) {
int[] cnt = new int[26];
for (int i = 0; i < 26; ++i) {
cnt[i] = cnt1[i] - cnt2[i];
if (cnt[i] < 0) {
return null;
}
}
return cnt;
}
}
// Accepted solution for LeetCode #2983: Palindrome Rearrangement Queries
func canMakePalindromeQueries(s string, queries [][]int) (ans []bool) {
n := len(s)
m := n / 2
t := reverse(s[m:])
s = s[:m]
pre1 := make([][]int, m+1)
pre2 := make([][]int, m+1)
diff := make([]int, m+1)
pre1[0] = make([]int, 26)
pre2[0] = make([]int, 26)
for i := 1; i <= m; i++ {
pre1[i] = slices.Clone(pre1[i-1])
pre2[i] = slices.Clone(pre2[i-1])
pre1[i][int(s[i-1]-'a')]++
pre2[i][int(t[i-1]-'a')]++
diff[i] = diff[i-1]
if s[i-1] != t[i-1] {
diff[i]++
}
}
for _, q := range queries {
a, b := q[0], q[1]
c, d := n-1-q[3], n-1-q[2]
if a <= c {
ans = append(ans, check(pre1, pre2, diff, a, b, c, d))
} else {
ans = append(ans, check(pre2, pre1, diff, c, d, a, b))
}
}
return
}
func check(pre1, pre2 [][]int, diff []int, a, b, c, d int) bool {
if diff[a] > 0 || diff[len(diff)-1]-diff[max(b, d)+1] > 0 {
return false
}
if d <= b {
return slices.Equal(count(pre1, a, b), count(pre2, a, b))
}
if b < c {
return diff[c]-diff[b+1] == 0 && slices.Equal(count(pre1, a, b), count(pre2, a, b)) && slices.Equal(count(pre1, c, d), count(pre2, c, d))
}
cnt1 := sub(count(pre1, a, b), count(pre2, a, c-1))
cnt2 := sub(count(pre2, c, d), count(pre1, b+1, d))
return !slices.Equal(cnt1, []int{}) && !slices.Equal(cnt2, []int{}) && slices.Equal(cnt1, cnt2)
}
func count(pre [][]int, i, j int) []int {
cnt := make([]int, 26)
for k := 0; k < 26; k++ {
cnt[k] = pre[j+1][k] - pre[i][k]
}
return cnt
}
func sub(cnt1, cnt2 []int) []int {
cnt := make([]int, 26)
for i := 0; i < 26; i++ {
cnt[i] = cnt1[i] - cnt2[i]
if cnt[i] < 0 {
return []int{}
}
}
return cnt
}
func reverse(s string) string {
runes := []rune(s)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
# Accepted solution for LeetCode #2983: Palindrome Rearrangement Queries
class Solution:
def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
def count(pre: List[List[int]], i: int, j: int) -> List[int]:
return [x - y for x, y in zip(pre[j + 1], pre[i])]
def sub(cnt1: List[int], cnt2: List[int]) -> List[int]:
res = []
for x, y in zip(cnt1, cnt2):
if x - y < 0:
return []
res.append(x - y)
return res
def check(
pre1: List[List[int]], pre2: List[List[int]], a: int, b: int, c: int, d: int
) -> bool:
if diff[a] > 0 or diff[m] - diff[max(b, d) + 1] > 0:
return False
if d <= b:
return count(pre1, a, b) == count(pre2, a, b)
if b < c:
return (
diff[c] - diff[b + 1] == 0
and count(pre1, a, b) == count(pre2, a, b)
and count(pre1, c, d) == count(pre2, c, d)
)
cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1))
cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d))
return bool(cnt1) and bool(cnt2) and cnt1 == cnt2
n = len(s)
m = n // 2
t = s[m:][::-1]
s = s[:m]
pre1 = [[0] * 26 for _ in range(m + 1)]
pre2 = [[0] * 26 for _ in range(m + 1)]
diff = [0] * (m + 1)
for i, (c1, c2) in enumerate(zip(s, t), 1):
pre1[i] = pre1[i - 1][:]
pre2[i] = pre2[i - 1][:]
pre1[i][ord(c1) - ord("a")] += 1
pre2[i][ord(c2) - ord("a")] += 1
diff[i] = diff[i - 1] + int(c1 != c2)
ans = []
for a, b, c, d in queries:
c, d = n - 1 - d, n - 1 - c
ok = (
check(pre1, pre2, a, b, c, d)
if a <= c
else check(pre2, pre1, c, d, a, b)
)
ans.append(ok)
return ans
// Accepted solution for LeetCode #2983: Palindrome Rearrangement Queries
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2983: Palindrome Rearrangement Queries
// class Solution {
// public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
// int n = s.length();
// int m = n / 2;
// String t = new StringBuilder(s.substring(m)).reverse().toString();
// s = s.substring(0, m);
// int[][] pre1 = new int[m + 1][0];
// int[][] pre2 = new int[m + 1][0];
// int[] diff = new int[m + 1];
// pre1[0] = new int[26];
// pre2[0] = new int[26];
// for (int i = 1; i <= m; ++i) {
// pre1[i] = pre1[i - 1].clone();
// pre2[i] = pre2[i - 1].clone();
// ++pre1[i][s.charAt(i - 1) - 'a'];
// ++pre2[i][t.charAt(i - 1) - 'a'];
// diff[i] = diff[i - 1] + (s.charAt(i - 1) == t.charAt(i - 1) ? 0 : 1);
// }
// boolean[] ans = new boolean[queries.length];
// for (int i = 0; i < queries.length; ++i) {
// int[] q = queries[i];
// int a = q[0], b = q[1];
// int c = n - 1 - q[3], d = n - 1 - q[2];
// ans[i] = a <= c ? check(pre1, pre2, diff, a, b, c, d)
// : check(pre2, pre1, diff, c, d, a, b);
// }
// return ans;
// }
//
// private boolean check(int[][] pre1, int[][] pre2, int[] diff, int a, int b, int c, int d) {
// if (diff[a] > 0 || diff[diff.length - 1] - diff[Math.max(b, d) + 1] > 0) {
// return false;
// }
// if (d <= b) {
// return Arrays.equals(count(pre1, a, b), count(pre2, a, b));
// }
// if (b < c) {
// return diff[c] - diff[b + 1] == 0 && Arrays.equals(count(pre1, a, b), count(pre2, a, b))
// && Arrays.equals(count(pre1, c, d), count(pre2, c, d));
// }
// int[] cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
// int[] cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));
// return cnt1 != null && cnt2 != null && Arrays.equals(cnt1, cnt2);
// }
//
// private int[] count(int[][] pre, int i, int j) {
// int[] cnt = new int[26];
// for (int k = 0; k < 26; ++k) {
// cnt[k] = pre[j + 1][k] - pre[i][k];
// }
// return cnt;
// }
//
// private int[] sub(int[] cnt1, int[] cnt2) {
// int[] cnt = new int[26];
// for (int i = 0; i < 26; ++i) {
// cnt[i] = cnt1[i] - cnt2[i];
// if (cnt[i] < 0) {
// return null;
// }
// }
// return cnt;
// }
// }
// Accepted solution for LeetCode #2983: Palindrome Rearrangement Queries
function canMakePalindromeQueries(s: string, queries: number[][]): boolean[] {
const n: number = s.length;
const m: number = n >> 1;
const t: string = s.slice(m).split('').reverse().join('');
s = s.slice(0, m);
const pre1: number[][] = Array.from({ length: m + 1 }, () => Array(26).fill(0));
const pre2: number[][] = Array.from({ length: m + 1 }, () => Array(26).fill(0));
const diff: number[] = Array(m + 1).fill(0);
for (let i = 1; i <= m; ++i) {
pre1[i] = [...pre1[i - 1]];
pre2[i] = [...pre2[i - 1]];
++pre1[i][s.charCodeAt(i - 1) - 'a'.charCodeAt(0)];
++pre2[i][t.charCodeAt(i - 1) - 'a'.charCodeAt(0)];
diff[i] = diff[i - 1] + (s[i - 1] === t[i - 1] ? 0 : 1);
}
const ans: boolean[] = Array(queries.length).fill(false);
for (let i = 0; i < queries.length; ++i) {
const q: number[] = queries[i];
const [a, b] = [q[0], q[1]];
const [c, d] = [n - 1 - q[3], n - 1 - q[2]];
ans[i] = a <= c ? check(pre1, pre2, diff, a, b, c, d) : check(pre2, pre1, diff, c, d, a, b);
}
return ans;
}
function check(
pre1: number[][],
pre2: number[][],
diff: number[],
a: number,
b: number,
c: number,
d: number,
): boolean {
if (diff[a] > 0 || diff[diff.length - 1] - diff[Math.max(b, d) + 1] > 0) {
return false;
}
if (d <= b) {
return arraysEqual(count(pre1, a, b), count(pre2, a, b));
}
if (b < c) {
return (
diff[c] - diff[b + 1] === 0 &&
arraysEqual(count(pre1, a, b), count(pre2, a, b)) &&
arraysEqual(count(pre1, c, d), count(pre2, c, d))
);
}
const cnt1: number[] | null = sub(count(pre1, a, b), count(pre2, a, c - 1));
const cnt2: number[] | null = sub(count(pre2, c, d), count(pre1, b + 1, d));
return cnt1 !== null && cnt2 !== null && arraysEqual(cnt1, cnt2);
}
function count(pre: number[][], i: number, j: number): number[] {
const cnt: number[] = new Array(26).fill(0);
for (let k = 0; k < 26; ++k) {
cnt[k] = pre[j + 1][k] - pre[i][k];
}
return cnt;
}
function sub(cnt1: number[], cnt2: number[]): number[] | null {
const cnt: number[] = new Array(26).fill(0);
for (let i = 0; i < 26; ++i) {
cnt[i] = cnt1[i] - cnt2[i];
if (cnt[i] < 0) {
return null;
}
}
return cnt;
}
function arraysEqual(arr1: number[], arr2: number[]): boolean {
return JSON.stringify(arr1) === JSON.stringify(arr2);
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.