DeepSeek LeetCode 3777. 使子字符串变交替的最少删除次数 Python3实现
没问题，这是 LeetCode 3777 的 Python 线段树解法。核心思路完全一致：通过线段树维护每个区间的左端点字符、右端点字符以及最小删除次数，合并时只需检查左右相邻字符是否相同。
```python
from typing import List
class Solution:
def minDeletions(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
arr = list(s) # 方便原地修改字符
tree = [None] * (4 * n + 5) # 线段树数组，每个节点存 (左字符, 右字符, 删除次数)
# ---------- 合并两个相邻区间 ----------
def merge(left, right):
if left is None:
return right
if right is None:
return left
lc, rc, cnt = left[0], right[1], left[2] + right[2]
# 左区间的右端点 和 右区间的左端点 相同，则必须在交界处删掉一个字符
if left[1] == right[0]:
cnt += 1
return (lc, rc, cnt)
# ---------- 建树 ----------
def build(idx, l, r):
if l == r:
tree[idx] = (arr[l], arr[l], 0)
return
mid = (l + r) // 2
build(idx * 2, l, mid)
build(idx * 2 + 1, mid + 1, r)
tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1])
# ---------- 单点更新（翻转字符） ----------
def update(idx, l, r, pos):
if l == r:
# A <-> B 翻转
arr[l] = 'B' if arr[l] == 'A' else 'A'
tree[idx] = (arr[l], arr[l], 0)
return
mid = (l + r) // 2
if pos <= mid:
update(idx * 2, l, mid, pos)
else:
update(idx * 2 + 1, mid + 1, r, pos)
tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1])
# ---------- 区间查询 ----------
def query(idx, l, r, ql, qr):
# 完全覆盖
if ql <= l and r <= qr:
return tree[idx]
mid = (l + r) // 2
# 只在左半部分
if qr <= mid:
return query(idx * 2, l, mid, ql, qr)
# 只在右半部分
if ql > mid:
return query(idx * 2 + 1, mid + 1, r, ql, qr)
# 跨越左右两部分，需要合并
left_res = query(idx * 2, l, mid, ql, qr)
right_res = query(idx * 2 + 1, mid + 1, r, ql, qr)
return merge(left_res, right_res)
# ---------- 处理查询 ----------
build(1, 0, n - 1)
ans = []
for q in queries:
if q[0] == 1: # 更新操作：[1, index]
update(1, 0, n - 1, q[1])
else: # 查询操作：[2, l, r]
res = query(1, 0, n - 1, q[1], q[2])
ans.append(res[2])
return ans
```
🧠 核心要点提醒
1. 合并逻辑：left.del + right.del + (1 if left.rc == right.lc else 0) 是解题关键，因为只有相邻边界会互相影响。
2. 复杂度：建树 O(n)，每次更新或查询均为 O(log n)，总复杂度 O((n + q) log n)，完美适配 10^5 数据量。
3. 索引说明：本解法默认 queries 中的下标是 0-based（LeetCode 标准），如果你的环境是 1-based，记得把更新和查询的索引都减 1。
如果对线段树合并的推导还有疑问，或者想看看其他写法（比如树状数组），可以随时告诉我，我再给你展开讲讲。😊