回文串重新排列查询

标签: 哈希表 字符串 前缀和

难度: Hard

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

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ai, bi, ci, di] 。

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

  • 将下标在范围 0 <= ai <= bi < n / 2 内的 子字符串 s[ai:bi] 中的字符重新排列。
  • 将下标在范围 n / 2 <= ci <= di < n 内的 子字符串 s[ci:di] 中的字符重新排列。

对于每个查询，你的任务是判断执行操作后能否让 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 个查询：
第一个查询：
- a0 = 1, b0 = 1, c0 = 3, d0 = 5
- 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。
- 为了让 s 变为回文串，s[3:5] 可以重新排列得到 => abccba 。
- 现在 s 是一个回文串。所以 answer[0] = true 。
第二个查询：
- a1 = 0, b1 = 2, c1 = 5, d1 = 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]
解释：这个示例中，只有一个查询。
a0 = 0, b0 = 2, c0 = 7, d0 = 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]
解释：这个示例中，只有一个查询。
a0 = 1, b0 = 2, c0 = 4, d0 = 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 <= 105
  • 1 <= queries.length <= 105
  • 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 是一个偶数。
  • s 只包含小写英文字母。

Submission

运行时间: 144 ms

内存: 49.1 MB

class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n=len(s)
        left,right=0,n-1
        count = [0]*26
        while left<right:
            count[ord(s[left])-97]+=1
            count[ord(s[right])-97]-=1
            left+=1
            right-=1
        m=len(queries)
        r = [False]*m
        for x in count:
            if x: return r 
        start,end=-1,-1
        for i in range(n//2):
            if s[i] != s[n-1-i]:
                if start == -1: start=i
                end=i
        if start == -1:
            return [True]*m
        rightIndices = [0]*(n//2 + 1)
        leftIndices = [0]*(n + 1)
        count = [0]*26
        right = n-1-start
        for i in range(start,n//2):
            count[ord(s[i])-97]+=1
            while count[ord(s[right])-97]>0:
                count[ord(s[right])-97]-=1
                right-=1
            rightIndices[i]=right
        count = [0]*26
        left = start
        for i in range(n-1-start,n//2 - 1,-1):
            count[ord(s[i])-97]+=1
            while count[ord(s[left])-97]>0:
                count[ord(s[left])-97]-=1
                left+=1
            leftIndices[i]=left
        for i in range(m):
            a,b,c,d = queries[i]
            if a<=start and b>=end or c<=n-1-end and d>=n-1-start or \
            a<=start and b>=start and c<=n-1-end and d>=rightIndices[b] or \
            c<=n-1-start and d>=n-1-start and a<=leftIndices[c] and b>=end:
                r[i]=True
        return r

Explain

题解的核心思路是预处理字符串 s，通过对比字符串的前半部和后半部的字符频率，找到最早和最晚的不匹配点。利用这些不匹配点，我们可以高效地回答每个查询。首先，我们创建一个字符频率数组 count 来统计从字符串两端向中心移动时，左右字符出现的差异。然后，针对查询，首先判断是否整个字符串已经满足回文结构。如果不满足，我们需要进一步确定最小的子字符串区间，使得这一区间内的所有字符重新排列后能够和其对应的镜像位置字符匹配。通过逐步检查从两端向中心移动过程中字符的匹配情况，我们建立了两个索引数组 leftIndices 和 rightIndices，这两个数组帮助我们迅速定位任意查询范围内是否可能通过排列实现回文结构。最后，对于每个查询，我们根据这些预处理的信息来判断是否能够重排成回文串。

时间复杂度: O(n + m)

空间复杂度: O(n + m)

class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        # 初始化计数数组和双指针
        count = [0] * 26
        left, right = 0, n - 1
        # 从两端向中心统计字符出现的差异
        while left < right:
            count[ord(s[left]) - 97] += 1
            count[ord(s[right]) - 97] -= 1
            left += 1
            right -= 1
        m = len(queries)
        r = [False] * m
        # 如果 count 中有非零元素，说明不能直接构成回文
        for x in count:
            if x: return r
        start, end = -1, -1
        # 确定最早和最晚的不匹配点
        for i in range(n//2):
            if s[i] != s[n-1-i]:
                if start == -1: start = i
                end = i
        if start == -1:
            return [True] * m
        rightIndices = [0] * (n//2 + 1)
        leftIndices = [0] * (n + 1)
        count = [0] * 26
        right = n - 1 - start
        # 确定可以匹配的右侧索引
        for i in range(start, n//2):
            count[ord(s[i]) - 97] += 1
            while count[ord(s[right]) - 97] > 0:
                count[ord(s[right]) - 97] -= 1
                right -= 1
            rightIndices[i] = right
        count = [0] * 26
        left = start
        # 确定可以匹配的左侧索引
        for i in range(n - 1 - start, n//2 - 1, -1):
            count[ord(s[i]) - 97] += 1
            while count[ord(s[left]) - 97] > 0:
                count[ord(s[left]) - 97] -= 1
                left += 1
            leftIndices[i] = left
        # 根据预处理结果判断每个查询是否能重排成回文串
        for i in range(m):
            a, b, c, d = queries[i]
            if a <= start and b >= end or c <= n - 1 - end and d >= n - 1 - start or \
               a <= start and b >= start and c <= n - 1 - end and d >= rightIndices[b] or \
               c <= n - 1 - start and d >= n - 1 - start and a <= leftIndices[c] and b >= end:
                r[i] = True
        return r

Explore

在题解中，‘最早和最晚的不匹配点’是通过比较字符串从两端向中心的字符来确定的。从字符串的首尾开始，逐对字符比较，第一对不相同的字符的位置被标记为‘最早的不匹配点’（start），最后一对不相同的字符的位置被标记为‘最晚的不匹配点’（end）。这两个点的确定是为了辅助判断字符串的某个子区间是否可以通过字符重新排列来形成回文。在处理查询时，如果查询的区间包含了这两个点，那么该区间内的字符需要进行详细检查，以确认是否所有字符都可以通过适当的重新排列来匹配其镜像位置的字符。

字符频率数组 count 用来记录字符串从两端到中心过程中字符出现的差异。数组初始化为全0，表示没有任何字符差异。随着从两端向中心遍历字符串，每次遍历时，左侧字符的频率在对应的 count 数组中增加，而右侧字符的频率减少。这种增减反映了在尝试构建回文时两侧字符出现的不平衡。如果数组中所有的值都能回归到0，说明可以通过某种排列形成回文串。这个数组的更新是基于每个字符出现次数的不平衡程度，从而帮助我们在后续的查询中快速判断重排的可能性。

start 和 end 索引标记了整个字符串中第一次和最后一次字符不匹配的位置。这意味着在这两个索引之间的区域是最有可能需要通过字符重排来达成回文的区域。在处理查询时，如果查询的区间完全包含从 start 到 end 的区间，这表明在考虑的子字符串中包含了所有潜在的不匹配字符。因此，只有当这部分区间可以通过重新排列来匹配其对称部分时，整个子字符串才可能被重排为回文。

复合条件语句用于判断查询的子区间是否可以通过重排成为回文结构。具体条件如下： 1. `a <= start && b >= end`：查询区间包含了从 start 到 end 的全部字符，这是重排成回文的必要条件之一。 2. `c <= n - 1 - end && d >= n - 1 - start`：确保子区间的镜像对称部分也包含在查询中，这对于形成对称的回文结构是必要的。 3. `a <= start && b >= start && c <= n - 1 - end && d >= rightIndices[b]`：确保左侧的查询区间至少包括到 start 且右侧的查询区间延伸到正确匹配右侧的相关索引，意味着这部分区间可以通过重排来匹配其镜像对称区域。 4. `c <= n - 1 - start && d >= n - 1 - start && a <= leftIndices[c] && b >= end`：确保右侧的查询区间至少包括到最远的不匹配点，而左侧的查询区间可以延伸到对应的左侧索引，这同样是为了保证可以通过重排来实现对称。 以上条件判断的组合确保了在回文构建过程中，查询的区间能够在逻辑上和结构上满足重排成回文的要求。