回文串重新排列查询
难度:
标签:
题目描述
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], where0 <= ai <= bi < n / 2. - Rearrange the characters within the substring
s[ci:di], wheren / 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 a 0-indexed array answer, where answer[i] == true if it is possible to make s a palindrome by performing operations specified by the ith 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 indexxto indexyins, 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: - a0 = 1, b0 = 1, c0 = 3, d0 = 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: - a1 = 0, b1 = 2, c1 = 5, d1 = 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. a0 = 0, b0 = 2, c0 = 7, d0 = 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. a0 = 1, b0 = 2, c0 = 4, d0 = 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 <= 1051 <= queries.length <= 105queries[i].length == 4ai == queries[i][0], bi == queries[i][1]ci == queries[i][2], di == queries[i][3]0 <= ai <= bi < n / 2n / 2 <= ci <= di < nnis even.sconsists of only lowercase English letters.
代码结果
运行时间: 144 ms, 内存: 49.1 MB
/*
思路：
1. 对于每个查询，我们将指定范围内的子字符串进行重新排列。
2. 检查重新排列后的字符串是否可以形成回文串。
3. 判断一个字符串是否可以成为回文串，只需检查每个字符出现的次数，最多只能有一个字符出现奇数次。
4. 使用Java Stream来优化代码结构。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean[] canMakePalindrome(String s, int[][] queries) {
return Arrays.stream(queries)
.map(query -> s.substring(query[0], query[1] + 1) + s.substring(query[2], query[3] + 1))
.map(this::canFormPalindrome)
.mapToBoolean(Boolean::booleanValue)
.toArray();
}
private boolean canFormPalindrome(String str) {
long oddCount = str.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(c -> c, Collectors.counting()))
.values()
.stream()
.filter(count -> count % 2 != 0)
.count();
return oddCount <= 1;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "abcabc";
int[][] queries = {{1, 1, 3, 5}, {0, 2, 5, 5}};
System.out.println(Arrays.toString(solution.canMakePalindrome(s, queries)));
}
}
解释
方法:
题解的核心思路是预处理字符串 s，通过对比字符串的前半部和后半部的字符频率，找到最早和最晚的不匹配点。利用这些不匹配点，我们可以高效地回答每个查询。首先，我们创建一个字符频率数组 count 来统计从字符串两端向中心移动时，左右字符出现的差异。然后，针对查询，首先判断是否整个字符串已经满足回文结构。如果不满足，我们需要进一步确定最小的子字符串区间，使得这一区间内的所有字符重新排列后能够和其对应的镜像位置字符匹配。通过逐步检查从两端向中心移动过程中字符的匹配情况，我们建立了两个索引数组 leftIndices 和 rightIndices，这两个数组帮助我们迅速定位任意查询范围内是否可能通过排列实现回文结构。最后，对于每个查询，我们根据这些预处理的信息来判断是否能够重排成回文串。
时间复杂度:
O(n + m)
空间复杂度:
O(n + m)
代码细节讲解
🦆
如何确定题解中提到的‘最早和最晚的不匹配点’，并且这些点如何影响到整个算法的查询处理过程？
▷🦆
题解中提到的预处理步骤中用到的字符频率数组 count 是如何初始化和更新的？具体是基于什么逻辑来调整 count 数组中的值？
▷🦆
为什么在处理每个查询时，需要依据 start 和 end 索引来判断子字符串是否可以通过重排成为回文结构？
▷🦆
题解最后判断单个查询是否能重排成回文串时，使用了复合条件语句，能否详细解释其中每个条件判断的意义和必要性？
▷