Hard

题目描述

给你一个长度为 n 的字符串 s，仅由字符 ‘A’ 和 ‘B’ 组成。

还给你一个长度为 q 的二维整数数组 queries，其中每个 queries[i] 是以下之一：

  • [1, j]：翻转字符串 s 中索引 j 处的字符，即 ‘A’ 变成 ‘B’（反之亦然）。此操作会改变 s 并影响后续查询。
  • [2, l, r]：计算使子串 s[l..r] 成为交替串所需的最小字符删除次数。此操作不会修改 s；s 的长度保持为 n。

如果没有两个相邻字符相等，则子串是交替的。长度为 1 的子串总是交替的。

返回一个整数数组 answer，其中 answer[i] 是第 i 个类型为 [2, l, r] 的查询的结果。

示例 1：

输入：s = “ABA”, queries = [[2,1,2],[1,1],[2,0,2]]

输出：[0,2]

示例 2：

输入：s = “ABB”, queries = [[2,0,2],[1,2],[2,0,2]]

输出：[1,0]

示例 3：

输入：s = “BABA”, queries = [[2,0,3],[1,1],[2,1,3]]

输出：[0,1]

提示：

  • 1 <= n == s.length <= 10^5
  • s[i] 是 ‘A’ 或 ‘B’
  • 1 <= q == queries.length <= 10^5
  • queries[i].length == 2 或 3
  • queries[i] == [1, j] 或 queries[i] == [2, l, r]
  • 0 <= j <= n - 1
  • 0 <= l <= r <= n - 1

解题思路

解题思路

这道题的核心思想是统计子串中相邻相同字符对的数量。要使字符串成为交替串，我们需要删除所有相邻相同的字符对中的一个字符。

关键洞察：

  1. 交替串特性：在交替串中，相邻字符必须不同
  2. 删除策略：每遇到一对相邻相同字符 s[i] == s[i-1]，我们需要删除其中一个
  3. 动态维护：使用树状数组（Fenwick Tree）高效处理区间求和和单点更新

算法步骤：

  1. 预处理：创建辅助数组 eq，其中 eq[i] = 1 表示 s[i] == s[i-1]（当 i >= 1 时）
  2. 建立树状数组：用于维护 eq 数组的前缀和，支持 O(log n) 的区间查询和单点更新
  3. 处理查询：
    • 类型1查询 [1, j]：翻转字符 s[j]，更新 eq[j] 和 eq[j+1]
    • 类型2查询 [2, l, r]：计算区间 [l+1, r] 的 eq 值之和

为什么这样做是正确的？

  • 子串 s[l..r] 中相邻相同字符对的数量就是需要删除的字符数
  • 每个相邻相同对删除一个字符就能使该位置变为交替
  • 树状数组保证了高效的区间查询和更新操作

时间复杂度：O((n + q) log n)，空间复杂度：O(n)

代码实现

class Solution {
public:
    vector<int> minDeletions(string s, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> eq(n, 0);
        
        // 初始化eq数组
        for (int i = 1; i < n; i++) {
            eq[i] = (s[i] == s[i-1]) ? 1 : 0;
        }
        
        // 树状数组
        vector<int> bit(n + 1, 0);
        
        auto update = [&](int idx, int val) {
            for (int i = idx; i <= n; i += i & (-i)) {
                bit[i] += val;
            }
        };
        
        auto query = [&](int idx) {
            int sum = 0;
            for (int i = idx; i > 0; i -= i & (-i)) {
                sum += bit[i];
            }
            return sum;
        };
        
        // 初始化树状数组
        for (int i = 1; i < n; i++) {
            update(i + 1, eq[i]);
        }
        
        vector<int> result;
        
        for (auto& q : queries) {
            if (q[0] == 1) {
                int j = q[1];
                s[j] = (s[j] == 'A') ? 'B' : 'A';
                
                // 更新eq[j]
                if (j >= 1) {
                    int oldVal = eq[j];
                    eq[j] = (s[j] == s[j-1]) ? 1 : 0;
                    update(j + 1, eq[j] - oldVal);
                }
                
                // 更新eq[j+1]
                if (j + 1 < n) {
                    int oldVal = eq[j + 1];
                    eq[j + 1] = (s[j + 1] == s[j]) ? 1 : 0;
                    update(j + 2, eq[j + 1] - oldVal);
                }
            } else {
                int l = q[1], r = q[2];
                int ans = 0;
                if (l < r) {
                    ans = query(r + 1) - query(l + 1);
                }
                result.push_back(ans);
            }
        }
        
        return result;
    }
};

class Solution:
    def minDeletions(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        s = list(s)  # 转换为可修改的列表
        eq = [0] * n
        
        # 初始化eq数组
        for i in range(1, n):
            eq[i] = 1 if s[i] == s[i-1] else 0
        
        # 树状数组
        bit = [0] * (n + 1)
        
        def update(idx, val):
            while idx <= n:
                bit[idx] += val
                idx += idx & (-idx)
        
        def query(idx):
            result = 0
            while idx > 0:
                result += bit[idx]
                idx -= idx & (-idx)
            return result
        
        # 初始化树状数组
        for i in range(1, n):
            update(i + 1, eq[i])
        
        result = []
        
        for q in queries:
            if q[0] == 1:
                j = q[1]
                s[j] = 'B' if s[j] == 'A' else 'A'
                
                # 更新eq[j]
                if j >= 1:
                    old_val = eq[j]
                    eq[j] = 1 if s[j] == s[j-1] else 0
                    update(j + 1, eq[j] - old_val)
                
                # 更新eq[j+1]
                if j + 1 < n:
                    old_val = eq[j + 1]
                    eq[j + 1] = 1 if s[j + 1] == s[j] else 0
                    update(j + 2, eq[j + 1] - old_val)
            else:
                l, r = q[1], q[2]
                ans = 0
                if l < r:
                    ans = query(r + 1) - query(l + 1)
                result.append(ans)
        
        return result

public class Solution {
    public int[] MinDeletions(string s, int[][] queries) {
        int n = s.Length;
        char[] chars = s.ToCharArray();
        int[] eq = new int[n];
        
        // 初始化eq数组
        for (int i = 1; i < n; i++) {
            eq[i] = chars[i] == chars[i-1] ? 1 : 0;
        }
        
        // 树状数组
        int[] bit = new int[n + 1];
        
        void Update(int idx, int val) {
            for (int i = idx; i <= n; i += i & (-i)) {
                bit[i] += val;
            }
        }
        
        int Query(int idx) {
            int sum = 0;
            for (int i = idx; i > 0; i -= i & (-i)) {
                sum += bit[i];
            }
            return sum;
        }
        
        // 初始化树状数组
        for (int i = 1; i < n; i++) {
            Update(i + 1, eq[i]);
        }
        
        List<int> result = new List<int>();
        
        foreach (var q in queries) {
            if (q[0] == 1) {
                int j = q[1];
                chars[j] = chars[j] == 'A' ? 'B' : 'A';
                
                // 更新eq[j]
                if (j >= 1) {
                    int oldVal = eq[j];
                    eq[j] = chars[j] == chars[j-1] ? 1 : 0;
                    Update(j + 1, eq[j] - oldVal);
                }
                
                // 更新eq[j+1]
                if (j + 1 < n) {
                    int oldVal = eq[j + 1];
                    eq[j + 1] = chars[j + 1] == chars[j] ? 1 : 0;
                    Update(j + 2, eq[j + 1] - oldVal);
                }
            } else {
                int l = q[1], r = q[2];
                int ans = 0;
                if (l < r) {
                    ans = Query(r + 1) - Query(l + 1);
                }
                result.Add(ans);
            }
        }
        
        return result.ToArray();
    }
}

var minDeletions = function(s, queries) {
    const n = s.length;
    const chars = s.split('');
    const eq = new Array(n).fill(0);
    
    // 初始化eq数组
    for (let i = 1; i < n; i++) {
        eq[i] = chars[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
预处理O(n)O(n)
每次查询O(log n)O(1)
每次更新O(log n)O(1)
总体O((n + q) log n)O(n)

其中 n 是字符串长度，q 是查询次数。树状数组的使用使得区间查询和单点更新都能在 O(log n) 时间内完成。