What is the core idea behind solving the Palindrome Rearrangement Queries problem?

The problem relies on efficiently checking if substrings of a string can be rearranged to form a palindrome using character frequency counts and prefix sums.

How can prefix sums improve the performance of this problem?

Prefix sums allow us to calculate the frequency of characters in any substring in constant time, significantly reducing the time complexity of each query.

What is the time complexity of the Palindrome Rearrangement Queries problem?

The time complexity is O(n + q), where n is the length of the string and q is the number of queries, assuming prefix sums are used for efficient query handling.

Can the solution be optimized further?

Yes, optimizing for space or handling more complex queries by using different data structures or algorithms could lead to further improvements.

What is the importance of hash tables in this problem?

Hash tables are crucial for counting character frequencies efficiently, which is the key step in determining whether substrings can be rearranged into a palindrome.

#2983

Hard

auto_awesome前缀和

LeetCode 题解工作台

回文串重新排列查询

给你一个长度为偶数 n ，下标从 0 开始的字符串 s 。同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [a i , b i , c i , d i ] 。对于每个查询 i ，你需要执行以下操作：将下标在范围 0 i i 内的子字符串 s[a…

哈希表字符串前缀和

题目描述

给你一个长度为偶数 n ，下标从 0 开始的字符串 s 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [a_i, b_i, c_i, d_i] 。

对于每个查询 i ，你需要执行以下操作：

将下标在范围 0 <= a_i <= b_i < n / 2 内的 子字符串 s[a_i:b_i] 中的字符重新排列。
将下标在范围 n / 2 <= c_i <= d_i < n 内的 子字符串 s[c_i:d_i] 中的字符重新排列。

对于每个查询，你的任务是判断执行操作后能否让 s 变成一个 回文串 。

每个查询与其他查询都是 独立的 。

请你返回一个下标从 0 开始的数组 answer ，如果第 i 个查询执行操作后，可以将 s 变为一个回文串，那么 answer[i] = true，否则为 false 。

子字符串 指的是一个字符串中一段连续的字符序列。
s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。

示例 1：

输入：s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]
输出：[true,true]
解释：这个例子中，有 2 个查询：
第一个查询：
- a₀ = 1, b₀ = 1, c₀ = 3, d₀ = 5
- 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。
- 为了让 s 变为回文串，s[3:5] 可以重新排列得到 => abccba 。
- 现在 s 是一个回文串。所以 answer[0] = true 。
第二个查询：
- a₁ = 0, b₁ = 2, c₁ = 5, d₁ = 5.
- 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。
- 为了让 s 变为回文串，s[0:2] 可以重新排列得到 => cbaabc 。
- 现在 s 是一个回文串，所以 answer[1] = true 。

示例 2：

输入：s = "abbcdecbba", queries = [[0,2,7,9]]
输出：[false]
解释：这个示例中，只有一个查询。
a₀ = 0, b₀ = 2, c₀ = 7, d₀ = 9.
你可以重新排列 s[0:2] => abbcdecbba 和 s[7:9] => abbcdecbba 。
无法通过重新排列这些子字符串使 s 变为一个回文串，因为 s[3:6] 不是一个回文串。
所以 answer[0] = false 。

示例 3：

输入：s = "acbcab", queries = [[1,2,4,5]]
输出：[true]
解释：这个示例中，只有一个查询。
a₀ = 1, b₀ = 2, c₀ = 4, d₀ = 5.
你可以重新排列 s[1:2] => acbcab 和 s[4:5] => acbcab 。
为了让 s 变为回文串，s[1:2] 可以重新排列得到 => abccab 。
然后 s[4:5] 重新排列得到 abccba 。
现在 s 是一个回文串，所以 answer[0] = true 。

提示：

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 是一个偶数。
s 只包含小写英文字母。

lightbulb

解题思路

方法一：前缀和 + 分类讨论

我们记字符串 $s$ 的长度为 $n$ ，那么一半的长度为 $m = \frac{n}{2}$ 。接下来，我们把字符串 $s$ 分成长度相等的两段，其中第二段反转后得到字符串 $t$ ，第一段记为 $s$ 。那么对于每个查询 $[a_i, b_i, c_i, d_i]$ ，其中 $c_i$ 和 $d_i$ 需要变换为 $n - 1 - d_i$ 和 $n - 1 - c_i$ 。问题转化为：对于每个查询 $[a_i, b_i, c_i, d_i]$ ，判断 $s[a_i, b_i]$ 和 $t[c_i, d_i]$ 是否可以通过重新排列，使得字符串 $s$ 和 $t$ 相等。

我们预处理以下信息：

字符串 $s$ 的前缀和数组 $pre_1$ ，其中 $pre_1[i][j]$ 表示字符串 $s$ 前 $i$ 个字符中字符 $j$ 的数量；
字符串 $t$ 的前缀和数组 $pre_2$ ，其中 $pre_2[i][j]$ 表示字符串 $t$ 前 $i$ 个字符中字符 $j$ 的数量；
字符串 $s$ 和 $t$ 的差异数组 $diff$ ，其中 $diff[i]$ 表示字符串 $s$ 和 $t$ 的前 $i$ 个字符中不同的字符数量。

对于每个查询 $[a_i, b_i, c_i, d_i]$ ，我们不妨假设 $a_i \le c_i$ ，那么我们需要讨论以下几种情况：

字符串 $s$ 和 $t$ 的前缀子串 $s[..a_i-1]$ 和 $t[..a_i-1]$ 必须相等，并且后缀子串 $s[\max(b_i, d_i)+1..]$ 和 $t[\max(b_i, d_i)..]$ 也必须相等，否则无法通过重新排列使得字符串 $s$ 和 $t$ 相等；
如果 $d_i \le b_i$ ，说明区间 $[a_i, b_i]$ 包含区间 $[c_i, d_i]$ ，那么如果 $s[a_i, b_i]$ 和 $t[a_i, b_i]$ 这两个子串包含的字符数量相同，那么就可以通过重新排列使得字符串 $s$ 和 $t$ 相等，否则无法通过重新排列使得字符串 $s$ 和 $t$ 相等；
如果 $b_i < c_i$ ，说明区间 $[a_i, b_i]$ 和区间 $[c_i, d_i]$ 不相交，那么 $s[b_i+1, c_i-1]$ 和 $t[b_i+1, c_i-1]$ 这两个子串必须相等，并且 $s[a_i, b_i]$ 和 $t[a_i, b_i]$ 这两个子串必须相等，同时 $s[c_i, d_i]$ 和 $t[c_i, d_i]$ 这两个子串必须相等，否则无法通过重新排列使得字符串 $s$ 和 $t$ 相等。
如果 $c_i \le b_i < d_i$ ，说明区间 $[a_i, b_i]$ 和区间 $[c_i, d_i]$ 相交，那么 $s[a_i, b_i]$ 包含的字符，减去 $t[a_i, c_i-1]$ 包含的字符，必须等于 $t[c_i, d_i]$ 包含的字符，减去 $s[b_i+1, d_i]$ 包含的字符，否则无法通过重新排列使得字符串 $s$ 和 $t$ 相等。

基于上述分析，我们遍历每个查询 $[a_i, b_i, c_i, d_i]$ ，判断是否满足上述条件即可。

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

49

50

51

52

53

54

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates the ability to efficiently solve range-based substring problems using hash tables.
question_mark
The candidate effectively utilizes prefix sums for fast query resolution.
question_mark
The candidate shows an understanding of palindrome conditions and string manipulation techniques.

warning

常见陷阱

外企场景

error
Failing to optimize the solution by not using prefix sums for frequency calculations.
error
Incorrectly checking for palindrome conditions, not accounting for multiple odd frequencies in the substrings.
error
Not managing large inputs effectively, leading to time complexity issues.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow for more than two substrings in each query.
arrow_right_alt
Extend the problem to handle queries involving substrings in the same half of the string.
arrow_right_alt
Implement a solution that minimizes the space complexity while still answering queries efficiently.

help

常见问题

外企场景

继续练习

#2949 统计美丽子字符串 II #2947 统计美丽子字符串 I #2982 找出出现至少三次的最长特殊子字符串 II