DeepSeek LeetCode 3777. 使子字符串变交替的最少删除次数 Java实现

这道题是 LeetCode 3777，题名为「使子字符串变交替的最少删除次数」(Minimum Deletions to Make Alternating Substring)。这是一道困难题，需要同时处理动态修改和区间查询。

📝 题目描述

· 输入：一个长度为 n 的字符串 s（仅含 'A'/'B'），和 q 个查询 queries。
· 操作类型：
· [1, j]：翻转 s[j]（A变B，B变A）。
· [2, l, r]：查询将子串 s[l..r] 变为交替字符串（相邻字符不同）所需的最少删除次数。
· 输出：按顺序返回所有 [2, l, r] 查询的结果数组。

💡 核心解法：线段树 (Segment Tree)

由于有高达 10^5 的单点更新和区间查询，需要一种能同时高效处理这两种操作的数据结构——线段树。

核心思路：对于任何区间，其最小删除次数可以分治合并。用线段树维护每个区间三个信息：

1. 左端点字符 (lc)
2. 右端点字符 (rc)
3. 最小删除次数 (del_cnt)

合并方法：合并左右子区间时，总删除次数 = 左区间删除次数 + 右区间删除次数 + （左区间右端点 == 右区间左端点 ? 1 : 0）。

💻 参考代码 (Java)

```java
class Solution {
// 线段树节点
static class Data {
char lc, rc; // 区间左右端点字符
int del; // 变成交替串的最小删除次数
Data(char lc, char rc, int del) { this.lc = lc; this.rc = rc; this.del = del; }
}

private Data[] tree;
private char[] chars;

public int[] minDeletions(String s, int[][] queries) {
int n = s.length();
this.chars = s.toCharArray();
// 线段树数组大小开4倍n
this.tree = new Data[4 * n];
build(1, 0, n - 1);

List<Integer> ansList = new ArrayList<>();
for (int[] q : queries) {
if (q[0] == 1) { // 更新操作
update(1, 0, n - 1, q[1]);
} else { // 查询操作
Data res = query(1, 0, n - 1, q[1], q[2]);
ansList.add(res.del);
}
}
return ansList.stream().mapToInt(i -> i).toArray();
}

// 合并两个节点信息
private Data merge(Data left, Data right) {
if (left == null) return right;
if (right == null) return left;
// 核心逻辑：左右相邻字符相同，则需多删一个
int add = (left.rc == right.lc) ? 1 : 0;
return new Data(left.lc, right.rc, left.del + right.del + add);
}

// 构建线段树
private void build(int node, int l, int r) {
if (l == r) {
tree[node] = new Data(chars[l], chars[l], 0);
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

// 单点更新（翻转字符）
private void update(int node, int l, int r, int idx) {
if (l == r) {
// 翻转字符：'A' <-> 'B'
chars[l] = (chars[l] == 'A') ? 'B' : 'A';
tree[node] = new Data(chars[l], chars[l], 0);
return;
}
int mid = (l + r) / 2;
if (idx <= mid) update(node * 2, l, mid, idx);
else update(node * 2 + 1, mid + 1, r, idx);
tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

// 区间查询
private Data query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[node];
int mid = (l + r) / 2;
if (qr <= mid) return query(node * 2, l, mid, ql, qr);
if (ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);
// 查询区间跨越左右子树，需要合并结果
Data leftRes = query(node * 2, l, mid, ql, qr);
Data rightRes = query(node * 2 + 1, mid + 1, r, ql, qr);
return merge(leftRes, rightRes);
}
}
```

⏱️ 复杂度分析

· 时间复杂度：
· 构建树：O(n)
· 每次更新或查询：O(log n)
· 总体：O((n + q) * log n)
· 空间复杂度：O(n)，主要是线段树数组开销。

理解“左右端点字符 + 删除次数”这个合并逻辑是关键。如果还有不清楚的地方，随时可以再问我。