2026-04-27：使子字符串变交替的最少删除次数。用go语言，给定一个只含字符 A 和 B 的字符串 s，长度为 n。随后会有若干操作查询 queries

福大大架构师每日一题

发布于 2026-04-28 19:45:32

710

2026-04-27：使子字符串变交替的最少删除次数。用go语言，给定一个只含字符 A 和 B 的字符串 s，长度为 n。随后会有若干操作查询 queries，总数为 q。每条查询可能是两种形式之一： 1.[1, j]：把字符串中位置 j 的字符翻转（A ↔ B）。该操作会改变字符串 s，并影响后续所有查询。 2.[2, l, r]：在不修改字符串 s 的前提下，针对区间 [l, r] 的子串，求让它变为“交替字符串”所需的最少删除字符数。

• “交替字符串”指子串中任意相邻两个字符都不相同。长度为 1 的子串天然满足该条件。
• 区间查询不会改变整体字符串长度 n。

请为所有类型 [2, l, r] 的查询依次计算结果，并把这些结果按顺序组成数组 answer 返回，其中 answer[i] 对应第 i 个区间查询的最小删除数。

1 <= n == s.length <= 100000。

s[i] 要么是 'A'，要么是 'B'。

1 <= q == queries.length <= 100000。

queries[i].length == 2 或 3。

queries[i] == [1, j] 或

queries[i] == [2, l, r]。

0 <= j <= n - 1。

0 <= l <= r <= n - 1。

输入：s = "ABA", queries = [[2,1,2],[1,1],[2,0,2]]。

输出：[0,2]。

解释：

i	queries[i]	j	l	r	查询前的 s	s[l..r]	结果	答案
0	[2, 1, 2]	-	1	2	"ABA"	"BA"	已经是交替字符串	0
1	[1, 1]	1	-	-	"ABA"	-	将 s[1] 从 'B' 反转为 'A'	-
2	[2, 0, 2]	-	0	2	"AAA"	"AAA"	删除任意两个 'A' 以得到 "A"	2

因此，答案是 [0, 2]。

题目来自力扣3777。

代码执行过程详细分步解析

我们结合输入示例：s = "ABA"（长度n=3），queries = [[2,1,2],[1,1],[2,0,2]]，分步骤拆解整个逻辑，全程不写代码，只讲核心流程。

前置知识铺垫

1. 交替字符串：相邻字符不能相同，比如BA是交替，AAA不是；
2. 核心规律：一个子串要变成交替字符串，最少删除次数 = 子串中相邻重复字符的总个数 例：BA无相邻重复，删除数=0；AAA有2组相邻重复（位置0-1、1-2），删除数=2；
3. 树状数组（Fenwick Tree）：专门用来快速记录、更新、查询区间内相邻重复字符的总数，支持O(logn)的单点修改和区间查询。

第一步：初始化数据结构

1. 确定字符串长度 n=3，创建一个长度适配的树状数组，专门存储相邻重复字符的标记；
2. 遍历原字符串 ABA，检查每一组相邻字符：
- • 位置0和1：A和B → 不重复，不标记；
- • 位置1和2：B和A → 不重复，不标记；
3. 最终树状数组中没有任何标记值，代表原字符串没有相邻重复的字符。

第二步：处理第一条查询 [2, 1, 2]（类型2：区间查询）

1. 解析查询：查询子串区间 [1,2]（对应原字符串BA）；
2. 核心逻辑：调用树状数组查询这个区间内相邻重复字符的总数；
3. 结果：区间内没有相邻重复字符，总数=0；
4. 输出：将0加入答案数组，此时答案数组为[0]。

第三步：处理第二条查询 [1, 1]（类型1：字符翻转）

1. 解析查询：翻转字符串位置1的字符（原字符是B，翻转后变成A）；
2. 关键操作：翻转字符会影响它左边和右边的相邻关系，需要同步更新树状数组：
- • 位置1的左侧是位置0（原字符A）：翻转后A和A重复 → 给树状数组标记+1；
- • 位置1的右侧是位置2（原字符A）：翻转后A和A重复 → 给树状数组标记+1；
3. 最终字符串变为AAA，树状数组记录了2个相邻重复标记；
4. 无输出结果，仅修改字符串和树状数组。

第四步：处理第三条查询 [2, 0, 2]（类型2：区间查询）

1. 解析查询：查询子串区间 [0,2]（对应修改后的字符串AAA）；
2. 核心逻辑：调用树状数组查询这个区间内相邻重复字符的总数；
3. 结果：区间内有2组相邻重复字符，总数=2；
4. 输出：将2加入答案数组，最终答案数组为[0, 2]。

完整流程总结

1. 初始化：用树状数组记录原字符串所有相邻重复字符的位置；
2. 遍历所有查询：
- • 遇到类型2查询：直接用树状数组查询目标区间的相邻重复总数，就是最少删除数，加入答案；
- • 遇到类型1查询：翻转指定位置的字符，同时更新该字符左右两侧的相邻关系（修改树状数组的标记）；
3. 所有查询处理完毕，返回答案数组。

时间复杂度与空间复杂度分析

1. 总时间复杂度

• 树状数组的单点更新和区间查询操作，时间复杂度都是 O(logn)；
• 初始化遍历字符串：O(n)；
• 总共有 q 条查询，每条查询最多执行2次树状数组操作（类型1）或1次（类型2）；
• 总时间复杂度：O(n + q·logn)。（完全适配题目中n和q最大1e5的要求，高效无超时）

2. 总额外空间复杂度

• 树状数组占用空间：O(n)；
• 存储原字符串的字节数组：O(n)；
• 答案数组：最多O(q)；
• 总额外空间复杂度：O(n + q)。（属于线性空间，符合大数据量的内存要求）

总结

1. 核心思路：最少删除次数 = 子串内相邻重复字符的个数；
2. 核心工具：树状数组实现快速修改+快速查询，适配1e5级别的大数据量；
3. 时间复杂度：O(n + q·logn)，空间复杂度：O(n + q)。

Go完整代码如下：

package main

import (
    "fmt"
)

type fenwick []int

func newFenwickTree(n int) fenwick {
    returnmake(fenwick, n+1) // 使用下标 1 到 n
}

// a[i] 增加 val
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) update(i int, val int) {
    for ; i < len(f); i += i & -i {
        f[i] += val
    }
}

// 求前缀和 a[1] + ... + a[i]
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) pre(i int) (res int) {
    for ; i > 0; i &= i - 1 {
        res += f[i]
    }
    return
}

// 求区间和 a[l] + ... + a[r]
// 1 <= l <= r <= n
// 时间复杂度 O(log n)
func (f fenwick) query(l, r int) int {
    if r < l {
        return0
    }
    return f.pre(r) - f.pre(l-1)
}

func minDeletions(s string, queries [][]int) (ans []int) {
    n := len(s)
    t := newFenwickTree(n - 1)
    for i := 1; i < n; i++ {
        if s[i-1] == s[i] { // 删除 i
            t.update(i, 1)
        }
    }

    bs := []byte(s)
    for _, q := range queries {
        if q[0] == 2 {
            ans = append(ans, t.query(q[1]+1, q[2]))
            continue
        }

        i := q[1]

        if i > 0 {
            val := 1
            if bs[i-1] == bs[i] {
                val = -1
            }
            t.update(i, val)
        }

        if i < n-1 {
            val := 1
            if bs[i] == bs[i+1] {
                val = -1
            }
            t.update(i+1, val)
        }

        bs[i] ^= 'A' ^ 'B'// A 变成 B，B 变成 A
    }
    return
}

func main() {
    s := "ABA"
    queries := [][]int{{2, 1, 2}, {1, 1}, {2, 0, 2}}
    result := minDeletions(s, queries)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)  # 使用下标 1 到 n

    # a[i] 增加 val
    # 1 <= i <= n
    # 时间复杂度 O(log n)
    def update(self, i: int, val: int) -> None:
        while i < len(self.bit):
            self.bit[i] += val
            i += i & -i

    # 求前缀和 a[1] + ... + a[i]
    # 1 <= i <= n
    # 时间复杂度 O(log n)
    def pre(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.bit[i]
            i &= i - 1
        return res

    # 求区间和 a[l] + ... + a[r]
    # 1 <= l <= r <= n
    # 时间复杂度 O(log n)
    def query(self, l: int, r: int) -> int:
        if r < l:
            return0
        return self.pre(r) - self.pre(l - 1)


def min_deletions(s: str, queries: list) -> list:
    n = len(s)
    tree = Fenwick(n - 1)

    # 初始化树状数组，标记需要删除的位置
    for i in range(1, n):
        if s[i - 1] == s[i]:  # 删除 i
            tree.update(i, 1)

    bs = list(s)
    ans = []

    for q in queries:
        if q[0] == 2:
            # 区间查询
            ans.append(tree.query(q[1] + 1, q[2]))
            continue

        # 更新操作 q[0] == 1
        i = q[1]

        if i > 0:
            val = 1
            if bs[i - 1] == bs[i]:
                val = -1
            tree.update(i, val)

        if i < n - 1:
            val = 1
            if bs[i] == bs[i + 1]:
                val = -1
            tree.update(i + 1, val)

        # 翻转字符 A <-> B
        bs[i] = chr(ord('A') + ord('B') - ord(bs[i]))

    return ans


def main():
    s = "ABA"
    queries = [[2, 1, 2], [1, 1], [2, 0, 2]]
    result = min_deletions(s, queries)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Fenwick {
private:
    vector<int> bit;
    int n;

public:
    Fenwick(int n) : n(n) {
        bit.resize(n + 1, 0); // 使用下标 1 到 n
    }

    // a[i] 增加 val
    // 1 <= i <= n
    // 时间复杂度 O(log n)
    void update(int i, int val) {
        for (; i < bit.size(); i += i & -i) {
            bit[i] += val;
        }
    }

    // 求前缀和 a[1] + ... + a[i]
    // 1 <= i <= n
    // 时间复杂度 O(log n)
    int pre(int i) {
        int res = 0;
        for (; i > 0; i &= i - 1) {
            res += bit[i];
        }
        return res;
    }

    // 求区间和 a[l] + ... + a[r]
    // 1 <= l <= r <= n
    // 时间复杂度 O(log n)
    int query(int l, int r) {
        if (r < l) {
            return0;
        }
        return pre(r) - pre(l - 1);
    }
};

vector<int> minDeletions(string s, vector<vector<int>>& queries) {
    int n = s.size();
    Fenwick tree(n - 1);

    // 初始化树状数组，标记需要删除的位置
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == s[i]) { // 删除 i
            tree.update(i, 1);
        }
    }

    vector<char> bs(s.begin(), s.end());
    vector<int> ans;

    for (auto& q : queries) {
        if (q[0] == 2) {
            // 区间查询
            ans.push_back(tree.query(q[1] + 1, q[2]));
            continue;
        }

        // 更新操作 q[0] == 1
        int i = q[1];

        if (i > 0) {
            int val = 1;
            if (bs[i - 1] == bs[i]) {
                val = -1;
            }
            tree.update(i, val);
        }

        if (i < n - 1) {
            int val = 1;
            if (bs[i] == bs[i + 1]) {
                val = -1;
            }
            tree.update(i + 1, val);
        }

        // 翻转字符 A <-> B
        // 'A' ^ 'B' 在 C++ 中是 1，因为 'A' 是 65，'B' 是 66，异或结果为 1
        // 所以 bs[i] ^= 1 可以实现 A(65) 变成 B(66)，B(66) 变成 A(65)
        bs[i] ^= 1;
    }

    return ans;
}

int main() {
    string s = "ABA";
    vector<vector<int>> queries = {{2, 1, 2}, {1, 1}, {2, 0, 2}};
    vector<int> result = minDeletions(s, queries);

    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << "]" << endl;

    return0;
}