Hard

题目描述

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

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

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

  • 重新排列子字符串 s[ai:bi] 内的字符，其中 0 <= ai <= bi < n / 2。
  • 重新排列子字符串 s[ci:di] 内的字符，其中 n / 2 <= ci <= di < n。

对于每个查询，你的任务是判断是否可以通过执行操作使 s 成为回文串。

每个查询都是独立回答的。

返回一个下标从 0 开始的数组 answer，其中如果可以通过执行第 i 个查询指定的操作使 s 成为回文串，那么 answer[i] == true，否则 answer[i] == false。

子字符串 是字符串中字符的连续序列。 s[x:y] 表示由 s 中从下标 x 到下标 y（都包含）的字符组成的子字符串。

示例 1：

输入：s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]
输出：[true,true]

示例 2：

输入：s = "abbcdecbba", queries = [[0,2,7,9]]
输出：[false]

示例 3：

输入：s = "acbcab", queries = [[1,2,4,5]]
输出：[true]

提示：

  • 2 <= n == s.length <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 4
  • 0 <= ai <= bi < n / 2
  • n / 2 <= ci <= di < n
  • n 是偶数
  • s 只包含小写英文字母

解题思路

这道题的核心思想是判断在允许重新排列指定区间的字符后，是否能构成回文串。

解题思路：

  1. 回文特性分析：对于回文串，字符串的左半部分与右半部分应该是镜像对称的。如果位置 i 对应位置 n-1-i，它们的字符应该相同。

  2. 区间处理策略：

    • 对于不在可重排区间内的位置，其字符必须与对称位置的字符相同
    • 对于在可重排区间内的位置，我们可以重新分配字符

  3. 字符频次统计：

    • 统计左侧可重排区间 [a,b] 的字符频次
    • 统计右侧可重排区间 [c,d] 的字符频次
    • 处理跨区间的对称关系

  4. 具体算法：

    • 对于每个查询，遍历所有对称位置对 (i, n-1-i)
    • 如果两个位置都不在可重排区间内，则必须字符相同
    • 如果一个在区间内一个不在，将不在区间内的字符从对应区间的频次中扣除
    • 如果两个都在区间内，不需要特殊处理
    • 最终检查左右两个区间的剩余字符频次是否相同

  5. 优化：使用前缀和优化字符频次的计算，避免重复统计。

这种方法的时间复杂度为 O(n * queries)，通过前缀和优化可以处理大规模数据。

代码实现

class Solution {
public:
    vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
        int n = s.length();
        int half = n / 2;
        
        // 预计算字符频次的前缀和
        vector<vector<int>> prefixLeft(half + 1, vector<int>(26, 0));
        vector<vector<int>> prefixRight(half + 1, vector<int>(26, 0));
        
        for (int i = 0; i < half; i++) {
            prefixLeft[i + 1] = prefixLeft[i];
            prefixLeft[i + 1][s[i] - 'a']++;
            
            prefixRight[i + 1] = prefixRight[i];
            prefixRight[i + 1][s[n - 1 - i] - 'a']++;
        }
        
        vector<bool> result;
        
        for (auto& query : queries) {
            int a = query[0], b = query[1], c = query[2], d = query[3];
            
            // 将右侧区间转换为左侧坐标系
            int c_mapped = n - 1 - d;
            int d_mapped = n - 1 - c;
            
            // 获取区间内的字符频次
            vector<int> leftCount(26, 0);
            vector<int> rightCount(26, 0);
            
            for (int i = a; i <= b; i++) {
                leftCount[s[i] - 'a']++;
            }
            
            for (int i = c; i <= d; i++) {
                rightCount[s[i] - 'a']++;
            }
            
            bool valid = true;
            
            // 检查所有对称位置
            for (int i = 0; i < half && valid; i++) {
                int j = n - 1 - i;
                
                bool leftInRange = (i >= a && i <= b);
                bool rightInRange = (j >= c && j <= d);
                
                if (!leftInRange && !rightInRange) {
                    // 两个都不在范围内，必须相同
                    if (s[i] != s[j]) {
                        valid = false;
                    }
                } else if (leftInRange && !rightInRange) {
                    // 左侧在范围内，右侧不在
                    leftCount[s[j] - 'a']--;
                    if (leftCount[s[j] - 'a'] < 0) {
                        valid = false;
                    }
                } else if (!leftInRange && rightInRange) {
                    // 左侧不在范围内，右侧在
                    rightCount[s[i] - 'a']--;
                    if (rightCount[s[i] - 'a'] < 0) {
                        valid = false;
                    }
                }
                // 两个都在范围内的情况不需要特殊处理
            }
            
            // 检查剩余字符频次是否匹配
            if (valid) {
                for (int i = 0; i < 26; i++) {
                    if (leftCount[i] != rightCount[i]) {
                        valid = false;
                        break;
                    }
                }
            }
            
            result.push_back(valid);
        }
        
        return result;
    }
};

class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        half = n // 2
        
        def solve_query(a, b, c, d):
            # 统计左侧和右侧区间的字符频次
            left_count = [0] * 26
            right_count = [0] * 26
            
            for i in range(a, b + 1):
                left_count[ord(s[i]) - ord('a')] += 1
                
            for i in range(c, d + 1):
                right_count[ord(s[i]) - ord('a')] += 1
            
            # 检查所有对称位置
            for i in range(half):
                j = n - 1 - i
                
                left_in_range = a <= i <= b
                right_in_range = c <= j <= d
                
                if not left_in_range and not right_in_range:
                    # 两个都不在范围内，必须相同
                    if s[i] != s[j]:
                        return False
                elif left_in_range and not right_in_range:
                    # 左侧在范围内，右侧不在
                    left_count[ord(s[j]) - ord('a')] -= 1
                    if left_count[ord(s[j]) - ord('a')] < 0:
                        return False
                elif not left_in_range and right_in_range:
                    # 左侧不在范围内，右侧在
                    right_count[ord(s[i]) - ord('a')] -= 1
                    if right_count[ord(s[i]) - ord('a')] < 0:
                        return False
                # 两个都在范围内的情况不需要特殊处理
            
            # 检查剩余字符频次是否匹配
            return left_count == right_count
        
        result = []
        for query in queries:
            a, b, c, d = query
            result.append(solve_query(a, b, c, d))
            
        return result

public class Solution {
    public bool[] CanMakePalindromeQueries(string s, int[][] queries) {
        int n = s.Length;
        int half = n / 2;
        
        bool[] result = new bool[queries.Length];
        
        for (int q = 0; q < queries.Length; q++) {
            int a = queries[q][0], b = queries[q][1];
            int c = queries[q][2], d = queries[q][3];
            
            // 统计字符频次
            int[] leftCount = new int[26];
            int[] rightCount = new int[26];
            
            for (int i = a; i <= b; i++) {
                leftCount[s[i] - 'a']++;
            }
            
            for (int i = c; i <= d; i++) {
                rightCount[s[i] - 'a']++;
            }
            
            bool valid = true;
            
            // 检查所有对称位置
            for (int i = 0; i < half && valid; i++) {
                int j = n - 1 - i;
                
                bool leftInRange = i >= a && i <= b;
                bool rightInRange = j >= c && j <= d;
                
                if (!leftInRange && !rightInRange) {
                    if (s[i] != s[j]) {
                        valid = false;
                    }
                } else if (leftInRange && !rightInRange) {
                    leftCount[s[j] - 'a']--;
                    if (leftCount[s[j] - 'a'] < 0) {
                        valid = false;
                    }
                } else if (!leftInRange && rightInRange) {
                    rightCount[s[i] - 'a']--;
                    if (rightCount[s[i] - 'a'] < 0) {
                        valid = false;
                    }
                }
            }
            
            // 检查剩余字符频次
            if (valid) {
                for (int i = 0; i < 26; i++) {
                    if (leftCount[i] != rightCount[i]) {
                        valid = false;
                        break;
                    }
                }
            }
            
            result[q] = valid;
        }
        
        return result;
    }
}

var canMakePalindromeQueries = function(s, queries) {
    const n = s.length;
    const half = Math.floor(n / 2);
    
    const solveQuery = (a, b, c, d) => {
        // 统计字符频次
        const leftCount = new Array(26).fill(0);
        const rightCount = new Array(26).fill(0);
        
        for (let i = a; i <= b; i++) {
            leftCount[s.charCodeAt(i) - 97]++;
        }
        
        for (let i = c; i <= d; i++) {
            rightCount[s.charCodeAt(i) - 97]++;
        }
        
        // 检查所有对称位置
        for (let i = 0; i < half; i++) {
            const j = n - 1 - i;
            
            const leftInRange = i >= a && i <= b;
            const rightInRange = j >= c && j <= d;
            
            if (!leftInRange && !rightInRange) {
                if (s[i] !== s[j]) {
                    return false;
                }
            } else if (leftInRange && !rightInRange) {
                leftCount[s.charCodeAt(j) - 97]--;
                if (leftCount[s.charCodeAt(j) - 97] < 0) {
                    return false;
                }
            } else if (!leftInRange && rightInRange) {
                rightCount[s.charCodeAt(i) - 97]--;
                if (rightCount[s.charCodeAt(i) - 97] < 0) {
                    return false;
                }
            }
        }
        
        // 检查剩余字符频次
        for (let i = 0; i < 26; i++) {
            if (leftCount[i] !== rightCount[i]) {
                return false;
            }
        }
        
        return true;
    };
    
    const result = [];
    for (const query of queries) {
        const [a, b, c, d] = query;
        result.push(solveQuery(a, b, c, d));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(q × n)
空间复杂度O(1)

其中 q 是查询数量，n 是字符串长度。对于每个查询，我们需要遍历字符串的一半来检查对称位置，字符频次统计和比较都是常数时间操作。

相关题目