Problem

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 _a0-indexed array _answer , whereanswer[i] == true if it is possible to makes a palindrome by performing operations specified by theith query, andfalse 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, both inclusive.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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] => a _b_ cabc and s[3:5] => abc _abc_.
- To make s a palindrome, s[3:5] can be rearranged to become => abc _cba_.
- 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] => _abc_ abc and s[5:5] => abcab _c_.
- To make s a palindrome, s[0:2] can be rearranged to become => _cba_ abc.
- Now, s is a palindrome. So, answer[1] = true.

Example 2

1
2
3
4
5
6
7

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] => _abb_ cdecbba and s[7:9] => abbcdec _bba_.
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

1
2
3
4
5
6
7
8

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] => a _cb_ cab and s[4:5] => acbc _ab_.
To make s a palindrome s[1:2] can be rearranged to become a _bc_ cab.
Then, s[4:5] can be rearranged to become abcc _ba_.
Now, s is a palindrome. So, answer[0] = true.

Constraints

  • 2 <= n == s.length <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 4
  • ai == queries[i][0], bi == queries[i][1]
  • ci == queries[i][2], di == queries[i][3]
  • 0 <= ai <= bi < n / 2
  • n / 2 <= ci <= di < n
  • n is even.
  • s consists of only lowercase English letters.

Solution

Method 1 – Prefix Sums and Frequency Matching

Intuition

To make the string a palindrome by rearranging two substrings, the first half and the reversed second half must have the same character counts after rearrangement. We can use prefix sums to quickly compute character frequencies for any substring, and for each query, check if the two halves can be rearranged to match.

Approach

  1. Precompute prefix sums of character counts for the left half and right half of the string.
  2. For each query, get the frequency of each character in the allowed left and right substrings.
  3. For the rest of the string (outside the allowed substrings), check if the characters at mirrored positions match (since they can’t be rearranged).
  4. For the allowed substrings, check if their character counts can be rearranged to match each other.
  5. If both conditions are satisfied, the answer is true; otherwise, false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
public:
    vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
        int n = s.size(), m = n/2;
        vector<vector<int>> preL(m+1, vector<int>(26)), preR(m+1, vector<int>(26));
        for (int i = 0; i < m; ++i) {
            preL[i+1] = preL[i];
            preL[i+1][s[i]-'a']++;
        }
        for (int i = m; i < n; ++i) {
            preR[i-m+1] = preR[i-m];
            preR[i-m+1][s[i]-'a']++;
        }
        vector<bool> ans;
        for (auto& q : queries) {
            int a=q[0], b=q[1], c=q[2]-m, d=q[3]-m;
            bool ok = true;
            for (int i = 0; i < a; ++i) {
                if (s[i] != s[n-1-i]) { ok = false; break; }
            }
            for (int i = b+1; i < m; ++i) {
                if (s[i] != s[n-1-i]) { ok = false; break; }
            }
            for (int i = 0; i < c; ++i) {
                if (s[m+i] != s[m-1-i]) { ok = false; break; }
            }
            for (int i = d+1; i < m; ++i) {
                if (s[m+i] != s[m-1-i]) { ok = false; break; }
            }
            if (!ok) { ans.push_back(false); continue; }
            vector<int> left(26), right(26);
            for (int j = 0; j < 26; ++j) {
                left[j] = preL[b+1][j] - preL[a][j];
                right[j] = preR[d+1][j] - preR[c][j];
            }
            sort(left.begin(), left.end());
            sort(right.begin(), right.end());
            ans.push_back(left == right);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

func canMakePalindromeQueries(s string, queries [][]int) []bool {
    n := len(s)
    m := n/2
    preL := make([][]int, m+1)
    preR := make([][]int, m+1)
    for i := range preL { preL[i] = make([]int, 26) }
    for i := range preR { preR[i] = make([]int, 26) }
    for i := 0; i < m; i++ {
        copy(preL[i+1], preL[i])
        preL[i+1][s[i]-'a']++
    }
    for i := m; i < n; i++ {
        copy(preR[i-m+1], preR[i-m])
        preR[i-m+1][s[i]-'a']++
    }
    ans := make([]bool, 0, len(queries))
    for _, q := range queries {
        a, b, c, d := q[0], q[1], q[2]-m, q[3]-m
        ok := true
        for i := 0; i < a; i++ {
            if s[i] != s[n-1-i] { ok = false; break }
        }
        for i := b+1; i < m; i++ {
            if s[i] != s[n-1-i] { ok = false; break }
        }
        for i := 0; i < c; i++ {
            if s[m+i] != s[m-1-i] { ok = false; break }
        }
        for i := d+1; i < m; i++ {
            if s[m+i] != s[m-1-i] { ok = false; break }
        }
        if !ok { ans = append(ans, false); continue }
        left := make([]int, 26)
        right := make([]int, 26)
        for j := 0; j < 26; j++ {
            left[j] = preL[b+1][j] - preL[a][j]
            right[j] = preR[d+1][j] - preR[c][j]
        }
        sort.Ints(left)
        sort.Ints(right)
        match := true
        for j := 0; j < 26; j++ {
            if left[j] != right[j] { match = false; break }
        }
        ans = append(ans, match)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public List<Boolean> canMakePalindromeQueries(String s, int[][] queries) {
        int n = s.length(), m = n/2;
        int[][] preL = new int[m+1][26], preR = new int[m+1][26];
        for (int i = 0; i < m; i++) {
            System.arraycopy(preL[i], 0, preL[i+1], 0, 26);
            preL[i+1][s.charAt(i)-'a']++;
        }
        for (int i = m; i < n; i++) {
            System.arraycopy(preR[i-m], 0, preR[i-m+1], 0, 26);
            preR[i-m+1][s.charAt(i)-'a']++;
        }
        List<Boolean> ans = new ArrayList<>();
        for (int[] q : queries) {
            int a=q[0], b=q[1], c=q[2]-m, d=q[3]-m;
            boolean ok = true;
            for (int i = 0; i < a; i++) if (s.charAt(i) != s.charAt(n-1-i)) { ok = false; break; }
            for (int i = b+1; i < m; i++) if (s.charAt(i) != s.charAt(n-1-i)) { ok = false; break; }
            for (int i = 0; i < c; i++) if (s.charAt(m+i) != s.charAt(m-1-i)) { ok = false; break; }
            for (int i = d+1; i < m; i++) if (s.charAt(m+i) != s.charAt(m-1-i)) { ok = false; break; }
            if (!ok) { ans.add(false); continue; }
            int[] left = new int[26], right = new int[26];
            for (int j = 0; j < 26; j++) {
                left[j] = preL[b+1][j] - preL[a][j];
                right[j] = preR[d+1][j] - preR[c][j];
            }
            Arrays.sort(left);
            Arrays.sort(right);
            ans.add(Arrays.equals(left, right));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    fun canMakePalindromeQueries(s: String, queries: Array<IntArray>): List<Boolean> {
        val n = s.length; val m = n/2
        val preL = Array(m+1) { IntArray(26) }
        val preR = Array(m+1) { IntArray(26) }
        for (i in 0 until m) {
            for (j in 0..25) preL[i+1][j] = preL[i][j]
            preL[i+1][s[i]-'a']++
        }
        for (i in m until n) {
            for (j in 0..25) preR[i-m+1][j] = preR[i-m][j]
            preR[i-m+1][s[i]-'a']++
        }
        val ans = mutableListOf<Boolean>()
        for (q in queries) {
            val (a, b, c0, d0) = q
            val c = c0-m; val d = d0-m
            var ok = true
            for (i in 0 until a) if (s[i] != s[n-1-i]) { ok = false; break }
            for (i in b+1 until m) if (s[i] != s[n-1-i]) { ok = false; break }
            for (i in 0 until c) if (s[m+i] != s[m-1-i]) { ok = false; break }
            for (i in d+1 until m) if (s[m+i] != s[m-1-i]) { ok = false; break }
            if (!ok) { ans.add(false); continue }
            val left = IntArray(26) { preL[b+1][it] - preL[a][it] }
            val right = IntArray(26) { preR[d+1][it] - preR[c][it] }
            left.sort(); right.sort()
            ans.add(left.contentEquals(right))
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def canMakePalindromeQueries(self, s: str, queries: list[list[int]]) -> list[bool]:
        n, m = len(s), len(s)//2
        preL = [[0]*26 for _ in range(m+1)]
        preR = [[0]*26 for _ in range(m+1)]
        for i in range(m):
            for j in range(26):
                preL[i+1][j] = preL[i][j]
            preL[i+1][ord(s[i])-97] += 1
        for i in range(m, n):
            for j in range(26):
                preR[i-m+1][j] = preR[i-m][j]
            preR[i-m+1][ord(s[i])-97] += 1
        ans = []
        for a, b, c0, d0 in queries:
            c, d = c0-m, d0-m
            ok = True
            for i in range(a):
                if s[i] != s[n-1-i]: ok = False; break
            for i in range(b+1, m):
                if s[i] != s[n-1-i]: ok = False; break
            for i in range(c):
                if s[m+i] != s[m-1-i]: ok = False; break
            for i in range(d+1, m):
                if s[m+i] != s[m-1-i]: ok = False; break
            if not ok: ans.append(False); continue
            left = [preL[b+1][j] - preL[a][j] for j in range(26)]
            right = [preR[d+1][j] - preR[c][j] for j in range(26)]
            ans.append(sorted(left) == sorted(right))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

impl Solution {
    pub fn can_make_palindrome_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<bool> {
        let n = s.len();
        let m = n/2;
        let s = s.as_bytes();
        let mut pre_l = vec![vec![0; 26]; m+1];
        let mut pre_r = vec![vec![0; 26]; m+1];
        for i in 0..m {
            pre_l[i+1].clone_from(&pre_l[i]);
            pre_l[i+1][(s[i]-b'a') as usize] += 1;
        }
        for i in m..n {
            pre_r[i-m+1].clone_from(&pre_r[i-m]);
            pre_r[i-m+1][(s[i]-b'a') as usize] += 1;
        }
        let mut ans = vec![];
        for q in queries {
            let (a, b, c, d) = (q[0] as usize, q[1] as usize, q[2] as usize - m, q[3] as usize - m);
            let mut ok = true;
            for i in 0..a { if s[i] != s[n-1-i] { ok = false; break; } }
            for i in b+1..m { if s[i] != s[n-1-i] { ok = false; break; } }
            for i in 0..c { if s[m+i] != s[m-1-i] { ok = false; break; } }
            for i in d+1..m { if s[m+i] != s[m-1-i] { ok = false; break; } }
            if !ok { ans.push(false); continue; }
            let mut left = vec![0; 26];
            let mut right = vec![0; 26];
            for j in 0..26 {
                left[j] = pre_l[b+1][j] - pre_l[a][j];
                right[j] = pre_r[d+1][j] - pre_r[c][j];
            }
            left.sort(); right.sort();
            ans.push(left == right);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    canMakePalindromeQueries(s: string, queries: number[][]): boolean[] {
        const n = s.length, m = n/2;
        const preL: number[][] = Array.from({length: m+1}, () => Array(26).fill(0));
        const preR: number[][] = Array.from({length: m+1}, () => Array(26).fill(0));
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < 26; j++) preL[i+1][j] = preL[i][j];
            preL[i+1][s.charCodeAt(i)-97]++;
        }
        for (let i = m; i < n; i++) {
            for (let j = 0; j < 26; j++) preR[i-m+1][j] = preR[i-m][j];
            preR[i-m+1][s.charCodeAt(i)-97]++;
        }
        const ans: boolean[] = [];
        for (const [a, b, c0, d0] of queries) {
            const c = c0-m, d = d0-m;
            let ok = true;
            for (let i = 0; i < a; i++) if (s[i] !== s[n-1-i]) { ok = false; break; }
            for (let i = b+1; i < m; i++) if (s[i] !== s[n-1-i]) { ok = false; break; }
            for (let i = 0; i < c; i++) if (s[m+i] !== s[m-1-i]) { ok = false; break; }
            for (let i = d+1; i < m; i++) if (s[m+i] !== s[m-1-i]) { ok = false; break; }
            if (!ok) { ans.push(false); continue; }
            const left = Array(26).fill(0), right = Array(26).fill(0);
            for (let j = 0; j < 26; j++) {
                left[j] = preL[b+1][j] - preL[a][j];
                right[j] = preR[d+1][j] - preR[c][j];
            }
            left.sort((a,b)=>a-b); right.sort((a,b)=>a-b);
            ans.push(left.join() === right.join());
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + q*26), where n is the length of s and q is the number of queries. Preprocessing is O(n), each query is O(26 log 26) for sorting and O(m) for checking fixed positions.
  • 🧺 Space complexity: O(n), for the prefix sum arrays.