2026-04-27：使子字符串变交替的最少删除次数。用go语言，给定一个只含字符 A 和 B 的字符串 s，长度为 n。随后会有若干操作查询 queries
🤖 AI总结
主题
使用树状数组解决字符串变交替的最少删除次数问题
摘要
通过树状数组快速计算子串相邻重复字符数，实现高效查询与更新，解决力扣3777题
关键信息
- 1 最少删除次数等于子串中相邻重复字符总数
- 2 树状数组支持O(logn)的更新和区间查询
- 3 示例输入输出展示了完整流程
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++完整代码如下：
using namespace std;
class Fenwick {
private:
vector 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 minDeletions(string s, 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 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 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;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
