构建回文串检测

1177. 构建回文串检测

给你一个字符串 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: vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) { } };

java 解法, 执行用时: 6 ms, 内存消耗: 92.2 MB, 提交时间: 2023-06-15 09:39:02

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        var sum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int bit = 1 << (s.charAt(i) - 'a');
            sum[i + 1] = sum[i] ^ bit; // 该比特对应字母的奇偶性：奇数变偶数，偶数变奇数
        }

        var ans = new ArrayList<Boolean>(queries.length); // 预分配空间
        for (var q : queries) {
            int left = q[0], right = q[1], k = q[2];
            int m = Integer.bitCount(sum[right + 1] ^ sum[left]);
            ans.add(m / 2 <= k);
        }
        return ans;
    }
}

golang 解法, 执行用时: 156 ms, 内存消耗: 20 MB, 提交时间: 2023-06-15 09:38:41

func canMakePaliQueries(s string, queries [][]int) []bool {
    sum := make([]uint32, len(s)+1) // 节省一半空间
    for i, c := range s {
        bit := uint32(1) << (c - 'a')
        sum[i+1] = sum[i] ^ bit // 该比特对应字母的奇偶性：奇数变偶数，偶数变奇数
    }

    ans := make([]bool, len(queries))
    for i, q := range queries {
        left, right, k := q[0], q[1], q[2]
        m := bits.OnesCount32(sum[right+1] ^ sum[left])
        ans[i] = m/2 <= k
    }
    return ans
}

golang 解法, 执行用时: 172 ms, 内存消耗: 49.3 MB, 提交时间: 2023-06-15 09:38:25

func canMakePaliQueries(s string, queries [][]int) []bool {
    sum := make([][26]int, len(s)+1)
    for i, c := range s {
        sum[i+1] = sum[i]
        sum[i+1][c-'a'] ^= 1 // 奇数变偶数，偶数变奇数
    }

    ans := make([]bool, len(queries))
    for i, q := range queries {
        left, right, k, m := q[0], q[1], q[2], 0
        for j := 0; j < 26; j++ {
            m += sum[right+1][j] ^ sum[left][j]
        }
        ans[i] = m/2 <= k
    }
    return ans
}

golang 解法, 执行用时: 180 ms, 内存消耗: 49.8 MB, 提交时间: 2023-06-15 09:38:14

func canMakePaliQueries(s string, queries [][]int) []bool {
    sum := make([][26]int, len(s)+1)
    for i, c := range s {
        sum[i+1] = sum[i]
        sum[i+1][c-'a']++
        sum[i+1][c-'a'] %= 2 // 偶数是 0
    }

    ans := make([]bool, len(queries))
    for i, q := range queries {
        left, right, k, m := q[0], q[1], q[2], 0
        for j := 0; j < 26; j++ {
            if sum[right+1][j] != sum[left][j] {
                m++
            }
        }
        ans[i] = m/2 <= k
    }
    return ans
}

golang 解法, 执行用时: 180 ms, 内存消耗: 49.1 MB, 提交时间: 2023-06-15 09:38:04

func canMakePaliQueries(s string, queries [][]int) []bool {
    sum := make([][26]int, len(s)+1)
    for i, c := range s {
        sum[i+1] = sum[i]
        sum[i+1][c-'a']++
    }

    ans := make([]bool, len(queries))
    for i, q := range queries {
        left, right, k, m := q[0], q[1], q[2], 0
        for j := 0; j < 26; j++ {
            m += (sum[right+1][j] - sum[left][j]) % 2 // 奇数+1，偶数+0
        }
        ans[i] = m/2 <= k
    }
    return ans
}

python3 解法, 执行用时: 156 ms, 内存消耗: 56.4 MB, 提交时间: 2023-06-15 09:37:41

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        sum = [0]
        for c in s:
            bit = 1 << (ord(c) - ord('a'))
            sum.append(sum[-1] ^ bit)  # 该比特对应字母的奇偶性：奇数变偶数，偶数变奇数

        ans = []
        for left, right, k in queries:
            m = (sum[left] ^ sum[right + 1]).bit_count()
            ans.append(m // 2 <= k)
        return ans

python3 解法, 执行用时: 628 ms, 内存消耗: 67.5 MB, 提交时间: 2023-06-15 09:37:26

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        sum = [[0] * 26]
        for c in s:
            sum.append(sum[-1].copy())
            sum[-1][ord(c) - ord('a')] ^= 1  # 奇数变偶数，偶数变奇数

        ans = []
        for left, right, k in queries:
            m = 0
            for sl, sr in zip(sum[left], sum[right + 1]):
                m += sr ^ sl
            ans.append(m // 2 <= k)
        return ans

python3 解法, 执行用时: 560 ms, 内存消耗: 67.3 MB, 提交时间: 2023-06-15 09:36:55

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        sum = [[0] * 26]
        for c in s:
            sum.append(sum[-1].copy())
            sum[-1][ord(c) - ord('a')] += 1
            sum[-1][ord(c) - ord('a')] %= 2  # 偶数是 0

        ans = []
        for left, right, k in queries:
            m = 0
            for sl, sr in zip(sum[left], sum[right + 1]):
                m += sr != sl
            ans.append(m // 2 <= k)
        return ans

python3 解法, 执行用时: 668 ms, 内存消耗: 70 MB, 提交时间: 2023-06-15 09:36:17

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        sum = [[0] * 26]
        for c in s:
            sum.append(sum[-1].copy())
            sum[-1][ord(c) - ord('a')] += 1

        ans = []
        for left, right, k in queries:
            m = 0
            for sl, sr in zip(sum[left], sum[right + 1]):
                m += (sr - sl) % 2  # 奇数+1，偶数+0
            ans.append(m // 2 <= k)
        return ans

上一题

下一题

详情