2983. Palindrome Rearrangement Queries

Description

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] = [a_i, b_i, c_i, d_i].

For each query i, you are allowed to perform the following operations:

Rearrange the characters within the substring s[a_i:b_i], where 0 <= a_i <= b_i < n / 2.
Rearrange the characters within the substring s[c_i:d_i], where n / 2 <= c_i <= d_i < 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 i^th 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, 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:
- a₀ = 1, b₀ = 1, c₀ = 3, d₀ = 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:
- a₁ = 0, b₁ = 2, c₁ = 5, d₁ = 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.
a₀ = 0, b₀ = 2, c₀ = 7, d₀ = 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.
a₀ = 1, b₀ = 2, c₀ = 4, d₀ = 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 <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 4
a_i == queries[i][0], b_i == queries[i][1]
c_i == queries[i][2], d_i == queries[i][3]
0 <= a_i <= b_i < n / 2
n / 2 <= c_i <= d_i < n
n is even.
s consists of only lowercase English letters.

Solutions

Solution 1: Prefix Sum + Case Discussion

Thinking

Each query may rearrange one segment in the left half and one in the right half, asking whether \(s\) can become a palindrome. With \(10^5\) queries this must be offline. Reverse the right half into \(t\); the question is whether the two rearrangeable ranges can make \(s\) and \(t\) identical.

Prefix letter counts compare multisets on those ranges; a prefix mismatch array \(diff\) checks that frozen positions already match. Cases (containment, disjoint, overlap) subtract the overlap and compare the remainders.

Let's denote the length of string \(s\) as \(n\), then half of the length is \(m = \frac{n}{2}\). Next, we divide string \(s\) into two equal-length segments, where the second segment is reversed to get string \(t\), and the first segment remains as \(s\). For each query \([a_i, b_i, c_i, d_i]\), where \(c_i\) and \(d_i\) need to be transformed to \(n - 1 - d_i\) and \(n - 1 - c_i\). The problem is transformed into: for each query \([a_i, b_i, c_i, d_i]\), determine whether \(s[a_i, b_i]\) and \(t[c_i, d_i]\) can be rearranged to make strings \(s\) and \(t\) equal.

We preprocess the following information:

The prefix sum array \(pre_1\) of string \(s\), where \(pre_1[i][j]\) represents the quantity of character \(j\) in the first \(i\) characters of string \(s\);
The prefix sum array \(pre_2\) of string \(t\), where \(pre_2[i][j]\) represents the quantity of character \(j\) in the first \(i\) characters of string \(t\);
The difference array \(diff\) of strings \(s\) and \(t\), where \(diff[i]\) represents the quantity of different characters in the first \(i\) characters of strings \(s\) and \(t\).

For each query \([a_i, b_i, c_i, d_i]\), let's assume \(a_i \le c_i\), then we need to discuss the following cases:

The prefix substrings \(s[..a_i-1]\) and \(t[..a_i-1]\) of strings \(s\) and \(t\) must be equal, and the suffix substrings \(s[\max(b_i, d_i)+1..]\) and \(t[\max(b_i, d_i)..]\) must also be equal, otherwise, it is impossible to rearrange to make strings \(s\) and \(t\) equal;
If \(d_i \le b_i\), it means the interval \([a_i, b_i]\) contains the interval \([c_i, d_i]\). If the substrings \(s[a_i, b_i]\) and \(t[a_i, b_i]\) contain the same quantity of characters, then it is possible to rearrange to make strings \(s\) and \(t\) equal, otherwise, it is impossible;
If \(b_i < c_i\), it means the intervals \([a_i, b_i]\) and \([c_i, d_i]\) do not intersect. Then the substrings \(s[b_i+1, c_i-1]\) and \(t[b_i+1, c_i-1]\) must be equal, and the substrings \(s[a_i, b_i]\) and \(t[a_i, b_i]\) must be equal, and the substrings \(s[c_i, d_i]\) and \(t[c_i, d_i]\) must be equal, otherwise, it is impossible to rearrange to make strings \(s\) and \(t\) equal.
If \(c_i \le b_i < d_i\), it means the intervals \([a_i, b_i]\) and \([c_i, d_i]\) intersect. Then the characters contained in \(s[a_i, b_i]\), minus the characters contained in \(t[a_i, c_i-1]\), must be equal to the characters contained in \(t[c_i, d_i]\), minus the characters contained in \(s[b_i+1, d_i]\), otherwise, it is impossible to rearrange to make strings \(s\) and \(t\) equal.

Based on the above analysis, we iterate through each query \([a_i, b_i, c_i, d_i]\), and determine whether it satisfies the above conditions.

Python3JavaC++GoTypeScript

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

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

class Solution {
public:
    vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
        int n = s.length();
        int m = n / 2;
        string t = string(s.begin() + m, s.end());
        reverse(t.begin(), t.end());
        s = string(s.begin(), s.begin() + m);

        vector<vector<int>> pre1(m + 1, vector<int>(26));
        vector<vector<int>> pre2(m + 1, vector<int>(26));
        vector<int> diff(m + 1, 0);
        for (int i = 1; i <= m; ++i) {
            pre1[i] = pre1[i - 1];
            pre2[i] = pre2[i - 1];
            ++pre1[i][s[i - 1] - 'a'];
            ++pre2[i][t[i - 1] - 'a'];
            diff[i] = diff[i - 1] + (s[i - 1] == t[i - 1] ? 0 : 1);
        }

        vector<bool> ans(queries.size(), false);
        for (int i = 0; i < queries.size(); ++i) {
            vector<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:
    bool check(const vector<vector<int>>& pre1, const vector<vector<int>>& pre2, const vector<int>& diff, int a, int b, int c, int d) {
        if (diff[a] > 0 || diff[diff.size() - 1] - 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 && count(pre1, a, b) == count(pre2, a, b) && count(pre1, c, d) == count(pre2, c, d);
        }

        vector<int> cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
        vector<int> cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));

        return cnt1 != vector<int>() && cnt2 != vector<int>() && cnt1 == cnt2;
    }

    vector<int> count(const vector<vector<int>>& pre, int i, int j) {
        vector<int> cnt(26);
        for (int k = 0; k < 26; ++k) {
            cnt[k] = pre[j + 1][k] - pre[i][k];
        }
        return cnt;
    }

    vector<int> sub(const vector<int>& cnt1, const vector<int>& cnt2) {
        vector<int> cnt(26);
        for (int i = 0; i < 26; ++i) {
            cnt[i] = cnt1[i] - cnt2[i];
            if (cnt[i] < 0) {
                return vector<int>();
            }
        }
        return cnt;
    }
};

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)
}

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);
}

2983. Palindrome Rearrangement Queries

Description

Solutions

Solution 1: Prefix Sum + Case Discussion

Comments