日期：2026年8月13日
LeetCode 題目連結：2213. Longest Substring of One Repeating Character
解題想法
困難題。題目給一個字串 $s$，長度為 $k$ 的字串 $queryCharacters$，長度為 $k$ 的整數陣列 $queryIndices$，第 $i$ 次查詢時會將 $s[queryIndices[i]]$ 改成 $queryCharacters[i]$，找出修改後的字串 $s$ 之中最長連續相同字母的子字串長度。由於這題 $s$ 最長為 $10^5$，查詢次數最多也是 $10^5$，如果每次修改 $s$ 之後都要從頭再找一次答案，這樣一定會超時。可以用線段樹 (segment tree) 解題，我一開始寫出來的 C++ 版本速度不快，將程式碼丟給 Gemini 詢問如何改寫程式碼才能加速，發現問題出在指標及配置記憶體花費太多時間，修改後速度快很多。
定義節點 Node class 或 struct，其中儲存了
- pre_len 從左端點開始的連續相同字元長度
- suf_len 從右端點開始的連續相同字元長度
- max_len 區間內最大連續長度
- total_len 區間總長度
- left_char 區間左端點的字元
- right_char 區間右端點的字元
- _build 內部函式，建立樹的內容。
- _merge 內部函式，合併節點。
- _update 內部函式，單點更新。
- update 外部函式，用來呼叫 _update。
- query_max 外部函式，回傳根節點的最大連續長度。
Python 程式碼
Runtime: 4167 ms, beats 16.40%. Memory: 85.56 MB, beats 31.15%.
class Node:
# 自訂節點類別
def __init__(self, pre_len=0, suf_len=0, max_len=0, left_char='', right_char='', total_len=0):
self.pre_len = pre_len # 從左端點開始的連續相同字元長度
self.suf_len = suf_len # 從右端點開始的連續相同字元長度
self.max_len = max_len # 區間內最大連續長度
self.left_char = left_char # 區間左端點的字元
self.right_char = right_char # 區間右端點的字元
self.total_len = total_len # 區間總長度
class SegmentTree:
# 自訂線段樹類別
def __init__(self, s):
self.n = len(s) # 長度
self.s = s # 字串
self.tree = [Node() for _ in range(4 * self.n)] # 樹的內容
# 呼叫內部函式 _build 建立樹，根節點索引值 1，左端點 0，右端點 n-1
self._build(1, 0, self.n - 1)
def _build(self, idx, start, end):
# 內部函式，索引值 idx，左端點 start，右端點 end
# 遞迴出口，左、右端點重合，建立新的節點
if start == end:
self.tree[idx] = Node(1, 1, 1, self.s[start], self.s[start], 1)
return
# 一般狀況，用遞迴建立左、右子節點
mid = (start + end) // 2 # 中點
self._build(2 * idx, start, mid) # 遞迴，建立左子節點
self._build(2 * idx + 1, mid + 1, end) # 遞迴，建立右子節點
self.tree[idx] = self._merge(self.tree[2 * idx], self.tree[2 * idx + 1]) # 合併左、右子節點成為父節點
def _merge(self, left, right):
# 內部函式，合併左、右子節點
res = Node() # 最後要回傳的節點
res.total_len = left.total_len + right.total_len # 更新線長度
res.left_char = left.left_char # 左端點字元
res.right_char = right.right_char # 右端點字元
res.pre_len = left.pre_len # 左端前綴長度
res.suf_len = right.suf_len # 右端後綴長度
res.max_len = max(left.max_len, right.max_len) # 更新最大長度
# 如果左右交界處字元相同，進行跨區合併
if left.right_char == right.left_char:
cross_len = left.suf_len + right.pre_len
res.max_len = max(res.max_len, cross_len)
# 如果左子節點是同一個字元，更新前綴長度
if left.pre_len == left.total_len:
res.pre_len = left.total_len + right.pre_len
# 如果右子節點是同一個字元，更新後綴長度
if right.suf_len == right.total_len:
res.suf_len = right.total_len + left.suf_len
return res # 回傳 res
def _update(self, idx, start, end, target, new_char):
# 內部函式，單點更新，目前處理節點索引值 idx，左端點 left，右端點 right，目標索引值 target，新的字元 new_char
# 遞迴出口，左、右端點重合，更新 self.tree[idx]
if start == end:
self.tree[idx] = Node(1, 1, 1, new_char, new_char, 1)
return
# 一般狀況，遞迴，找到 target 之後再往上層更新父節點
mid = (start + end) // 2 # 中點
if target <= mid: # 目標在左側
self._update(2 * idx, start, mid, target, new_char)
else: # 目標在右側
self._update(2 * idx + 1, mid + 1, end, target, new_char)
self.tree[idx] = self._merge(self.tree[2 * idx], self.tree[2 * idx + 1]) # 合併
def update(self, target, new_char):
# 外部函式，呼叫 self._update
self._update(1, 0, self.n - 1, target, new_char)
def query_max(self):
# 回傳根節點的最大連續重複長度
return self.tree[1].max_len
class Solution:
def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
# 初始化線段樹物件
tree = SegmentTree(s)
ans = []
# 處理更新及查詢
for new_char, target in zip(queryCharacters, queryIndices):
# 單點更新
tree.update(target, new_char)
# 查詢目前整體的最長連續重複字元長度
ans.append(tree.query_max())
return ans
C++ 程式碼
使用指標及 new，速度很慢。Runtime: 1259 ms, beats 5.37%. Memory: 527.82 MB, beats 5.37%.
/* 自訂節點類別 */
class Node {
public:
int pre_len; // 從左端點開始的連續相同字元長度
int suf_len; // 從右端點開始的連續相同字元長度
int max_len; // 區間內最大連續長度
int total_len; // 區間總長度
char left_char; // 區間左端點的字元
char right_char; // 區間右端點的字元
Node(int pre=1, int suf=1, int maxL=1, char left_ch=' ', char right_ch=' ', int tot=1) {
pre_len = pre;
suf_len = suf;
max_len = maxL;
left_char = left_ch;
right_char = right_ch;
total_len = tot;
}
};
/* 自訂線段樹類別 */
class SegmentTree {
private:
int n; // 長度
string s; // 字串
vector<Node*> tree; // 樹的內容
void _build(int idx, int start, int end) {
// 內部函式，索引值 idx，左端點 start，右端點 end
// 遞迴出口，左、右端點重合，建立新的節點
if (start == end) {
tree[idx] = new Node(1, 1, 1, s[start], s[start], 1);
return;
}
// 一般狀況，用遞迴建立左、右子節點
int mid = (end - start) / 2 + start; // 中點
_build(2 * idx, start, mid); // 遞迴，建立左子節點
_build(2 * idx + 1, mid + 1, end); // 遞迴，建立右子節點
tree[idx] = _merge(tree[2 * idx], tree[2 * idx + 1]); // 合併左、右子節點成為父節點
}
Node* _merge(Node* left, Node* right) {
// 內部函式，合併左、右子節點
Node* res = new Node(); // 最後要回傳的節點
res->total_len = left->total_len + right->total_len; // 更新線長度
res->left_char = left->left_char; // 左端點字元
res->right_char = right->right_char; // 右端點字元
res->pre_len = left->pre_len; // 左端前綴長度
res->suf_len = right->suf_len; // 右端後綴長度
res->max_len = max(left->max_len, right->max_len); // 更新最大長度
// 如果左右交界處字元相同，進行跨區合併
if (left->right_char == right->left_char) {
int cross_len = left->suf_len + right->pre_len;
res->max_len = max(res->max_len, cross_len);
// 如果左子節點是同一個字元，更新前綴長度
if (left->pre_len == left->total_len) {
res->pre_len = left->total_len + right->pre_len;
}
// 如果右子節點是同一個字元，更新後綴長度
if (right->suf_len == right->total_len) {
res->suf_len = right->total_len + left->suf_len;
}
}
return res; // 回傳 res
}
void _update(int idx, int start, int end, int target, char new_char) {
// 內部函式，單點更新，目前處理節點索引值 idx，左端點 left，右端點 right，目標索引值 target，新的字元 new_char
// 遞迴出口，左、右端點重合，更新 self.tree[idx]
if (start == end) {
tree[idx] = new Node(1, 1, 1, new_char, new_char, 1);
return;
}
// 一般狀況，遞迴，找到 target 之後再往上層更新父節點
int mid = (end - start) / 2 + start; // 中點
if (target <= mid) { // 目標在左側
_update(2 * idx, start, mid, target, new_char);
} else { // 目標在右側
_update(2 * idx + 1, mid + 1, end, target, new_char);
}
tree[idx] = _merge(tree[2 * idx], tree[2 * idx + 1]); // 合併
}
public:
SegmentTree(const string& t) {
// 初始化，輸入字串 t，建立線段樹的內容
n = (int)t.size();
s = t;
tree.assign(4*n, new Node());
_build(1, 0, n-1);
}
void update(int target, char new_char) {
// 外部函式，呼叫 _update
_update(1, 0, n - 1, target, new_char);
}
int query_max() {
// 回傳根節點的最大連續重複長度
return tree[1]->max_len;
}
};
class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
// 初始化線段樹物件
SegmentTree* tree = new SegmentTree(s);
int m = (int)queryIndices.size();
vector<int> ans (m, 0);
// 處理更新及查詢
for(int i = 0; i < m; i++) {
char new_char = queryCharacters[i];
int target = queryIndices[i];
// 單點更新
tree->update(target, new_char);
// 查詢目前整體的最長連續重複字元長度
ans[i] = tree->query_max();
}
return ans;
}
};
修改後的程式碼，速度快很多。Runtime: 164 ms, beats 61.75%. Memory: 110.38 MB, beats 50.34%.
/* 自訂節點結構體 */
struct Node {
int pre_len; // 從左端點開始的連續相同字元長度
int suf_len; // 從右端點開始的連續相同字元長度
int max_len; // 區間內最大連續長度
int total_len; // 區間總長度
char left_char; // 區間左端點的字元
char right_char; // 區間右端點的字元
// 建構子
Node(int pre=1, int suf=1, int maxL=1, char left_ch=' ', char right_ch=' ', int tot=1)
: pre_len(pre), suf_len(suf), max_len(maxL), left_char(left_ch), right_char(right_ch), total_len(tot) {}
};
/* 自訂線段樹類別 */
class SegmentTree {
private:
int n; // 長度
string s; // 字串
vector<Node> tree; // 樹的內容，不要用指標，速度比較快
void _build(int idx, int start, int end) {
// 內部函式，索引值 idx，左端點 start，右端點 end
// 遞迴出口，左、右端點重合，建立新的節點
if (start == end) {
tree[idx] = Node(1, 1, 1, s[start], s[start], 1);
return;
}
// 一般狀況，用遞迴建立左、右子節點
int mid = (end - start) / 2 + start; // 中點
_build(2 * idx, start, mid); // 遞迴，建立左子節點
_build(2 * idx + 1, mid + 1, end); // 遞迴，建立右子節點
tree[idx] = _merge(tree[2 * idx], tree[2 * idx + 1]); // 合併左、右子節點成為父節點
}
Node _merge(const Node& left, const Node& right) {
// 內部函式，合併左、右子節點，不要用指標
Node res; // 最後要回傳的節點，不要用 new
res.total_len = left.total_len + right.total_len; // 更新線長度
res.left_char = left.left_char; // 左端點字元
res.right_char = right.right_char; // 右端點字元
res.pre_len = left.pre_len; // 左端前綴長度
res.suf_len = right.suf_len; // 右端後綴長度
res.max_len = max(left.max_len, right.max_len); // 更新最大長度
// 如果左右交界處字元相同，進行跨區合併
if (left.right_char == right.left_char) {
int cross_len = left.suf_len + right.pre_len;
res.max_len = max(res.max_len, cross_len);
// 如果左子節點是同一個字元，更新前綴長度
if (left.pre_len == left.total_len) {
res.pre_len = left.total_len + right.pre_len;
}
// 如果右子節點是同一個字元，更新後綴長度
if (right.suf_len == right.total_len) {
res.suf_len = right.total_len + left.suf_len;
}
}
return res; // 回傳 res
}
void _update(int idx, int start, int end, int target, char new_char) {
// 內部函式，單點更新，目前處理節點索引值 idx，左端點 left，右端點 right，目標索引值 target，新的字元 new_char
// 遞迴出口，左、右端點重合，更新 self.tree[idx]
if (start == end) {
tree[idx] = Node(1, 1, 1, new_char, new_char, 1);
return;
}
// 一般狀況，遞迴，找到 target 之後再往上層更新父節點
int mid = (end - start) / 2 + start; // 中點
if (target <= mid) { // 目標在左側
_update(2 * idx, start, mid, target, new_char);
} else { // 目標在右側
_update(2 * idx + 1, mid + 1, end, target, new_char);
}
tree[idx] = _merge(tree[2 * idx], tree[2 * idx + 1]); // 合併
}
public:
SegmentTree(const string& t) {
// 初始化，輸入字串 t，建立線段樹的內容
n = (int)t.size();
s = t;
tree.resize(4*n);
_build(1, 0, n-1);
}
void update(int target, char new_char) {
// 外部函式，呼叫 _update
_update(1, 0, n - 1, target, new_char);
}
int query_max() {
// 回傳根節點的最大連續重複長度
return tree[1].max_len;
}
};
class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
// 初始化線段樹物件
SegmentTree tree(s); // 不要用 new
int m = (int)queryIndices.size();
vector<int> ans (m, 0);
// 處理更新及查詢
for(int i = 0; i < m; i++) {
char new_char = queryCharacters[i];
int target = queryIndices[i];
// 單點更新
tree.update(target, new_char);
// 查詢目前整體的最長連續重複字元長度
ans[i] = tree.query_max();
}
return ans;
}
};
沒有留言:
張貼留言