原文链接: https://leetcode-cn.com/problems/can-make-palindrome-from-substring

英文原文

You are given a string s and array queries where queries[i] = [lefti, righti, ki]. We may rearrange the substring s[lefti...righti] for each query and then choose up to ki of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return a boolean array answer where answer[i] is the result of the ith query queries[i].

Note that each letter is counted individually for replacement, so if, for example s[lefti...righti] = "aaa", and ki = 2, we can only replace two of the letters. Also, note that no query modifies the initial string s.

 

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0]: substring = "d", is palidrome.
queries[1]: substring = "bc", is not palidrome.
queries[2]: substring = "abcd", is not palidrome after replacing only 1 character.
queries[3]: substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4]: substring = "abcda", could be changed to "abcba" which is palidrome.

Example 2:

Input: s = "lyb", queries = [[0,1,0],[2,2,1]]
Output: [false,true]

 

Constraints:

• 1 <= s.length, queries.length <= 105
• 0 <= lefti <= righti < s.length
• 0 <= ki <= s.length
• s consists of lowercase English letters.

中文题目

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。 

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

 

示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

 

提示：

• 1 <= s.length, queries.length <= 10^5
• 0 <= queries[i][0] <= queries[i][1] < s.length
• 0 <= queries[i][2] <= s.length
• s 中只有小写英文字母

通过代码

高赞题解

解题思路

代码

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Boolean> result = new ArrayList<>();
        int cur = 0;
        int[] states = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            cur ^= (1 << (s.charAt(i) - 'a'));
            states[i] = cur;
        }
        for (int i = 0; i < queries.length; i++) {
            int ostate = queries[i][0] > 0 ? states[queries[i][0] - 1] : 0;
            int state = ostate ^ states[queries[i][1]];
            int cnt = 0;
            while (state != 0) {
                if ((state & 1) == 1) cnt++;
                state >>= 1;
            }
//            System.out.println(cnt);
            result.add(cnt / 2 <= queries[i][2]);
        }
        return result;
    }
}

统计信息

通过次数	提交次数	AC比率
6339	23613	26.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言