2213. Longest Substring of One Repeating Character

s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
Output: [3,3,4]

// 演算法：線段樹。每個節點存這段的最長同字元段(best)、前綴(pref)、後綴(suf)、
// 長度(len) 與左右端字元(lc/rc)。合併時特別處理「跨越左右邊界」的段。
// Algorithm: segment tree. Each node stores the best single-char run, plus prefix/
// suffix runs, length, and boundary chars, so a run crossing the split is handled.

#include <string.h>   // strlen
#include <stdlib.h>   // malloc / free

// 一個線段樹節點要記錄的所有資訊 / all info a segment-tree node keeps
typedef struct {
    int pref;   // 從左端算起、同字元的最長前綴長度 / longest same-char prefix length
    int suf;    // 到右端為止、同字元的最長後綴長度 / longest same-char suffix length
    int best;   // 這段區間內部的最長同字元段 / best single-char run inside this segment
    int len;    // 這段區間的長度 / length of this segment
    char lc;    // 這段最左邊的字元 / leftmost character of this segment
    char rc;    // 這段最右邊的字元 / rightmost character of this segment
} Node;

// 把左子節點 a 與右子節點 b 合併成父節點 / merge left child a and right child b into a parent
static Node merge(Node a, Node b) {
    Node r;                                 // r 是要回傳的父節點 / r is the parent to return
    r.len = a.len + b.len;                  // 父長度 = 兩段長度相加 / parent length = sum of the two
    r.lc  = a.lc;                           // 父最左字元 = 左子最左字元 / parent's left char = left child's left char
    r.rc  = b.rc;                           // 父最右字元 = 右子最右字元 / parent's right char = right child's right char

    r.pref = a.pref;                        // 前綴預設等於左子的前綴 / prefix defaults to left child's prefix
    // 若左子整段同一字元，且左子右端字元 == 右子左端字元，前綴可延伸進右子
    // If the left child is all one char AND its right char equals the right child's left char, extend
    if (a.pref == a.len && a.rc == b.lc)
        r.pref = a.len + b.pref;            // 吃進右子的前綴 / absorb right child's prefix

    r.suf = b.suf;                          // 後綴預設等於右子的後綴 / suffix defaults to right child's suffix
    // 對稱地：若右子整段同字元，且右子左端 == 左子右端，後綴延伸進左子
    // Symmetric: extend the suffix into the left child when possible
    if (b.suf == b.len && b.lc == a.rc)
        r.suf = b.len + a.suf;              // 吃進左子的後綴 / absorb left child's suffix

    r.best = a.best > b.best ? a.best : b.best;  // 先取兩子答案的較大者 / start from max of children's best
    if (a.rc == b.lc) {                     // 邊界兩字元相同才可能有跨界段 / a crossing run needs matching boundary chars
        int cross = a.suf + b.pref;         // 跨界段 = 左後綴 + 右前綴 / crossing run = left suffix + right prefix
        if (cross > r.best) r.best = cross; // 若更長就更新 / take it if longer
    }
    return r;                               // 回傳合併結果 / return the merged node
}

// 建樹：node 是樹陣列的下標，[l,r] 是這個節點負責的區間
// Build: node is the array index, [l,r] is the range this node covers
static void build(Node* tree, char* s, int node, int l, int r) {
    if (l == r) {                           // 葉子：只負責一個字元 / leaf: covers a single character
        tree[node].pref = tree[node].suf = tree[node].best = tree[node].len = 1;  // 單字元各值皆為 1 / all length-like fields are 1
        tree[node].lc = tree[node].rc = s[l];  // 左右端都是這個字元 / both ends are this character
        return;
    }
    int mid = (l + r) / 2;                  // 取中點把區間對半 / split the range in half at mid
    build(tree, s, 2 * node,     l,     mid);   // 遞迴建左半 (下標 2*node) / build left half (index 2*node)
    build(tree, s, 2 * node + 1, mid + 1, r);   // 遞迴建右半 (下標 2*node+1) / build right half (index 2*node+1)
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);  // 由兩子合併出本節點 / combine children into this node
}

// 單點更新：把位置 pos 的字元改成 c，並沿路往上重算
// Point update: set the char at position pos to c, then recompute up the path
static void update(Node* tree, int node, int l, int r, int pos, char c) {
    if (l == r) {                           // 到達目標葉子 / reached the target leaf
        tree[node].lc = tree[node].rc = c;  // 更新這個字元 / update the character (len/pref/suf/best stay 1)
        return;
    }
    int mid = (l + r) / 2;                  // 中點 / midpoint
    if (pos <= mid) update(tree, 2 * node,     l,     mid, pos, c);  // 目標在左半就往左走 / go left if pos is in the left half
    else            update(tree, 2 * node + 1, mid + 1, r, pos, c);  // 否則往右走 / otherwise go right
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);  // 子節點變了，重算本節點 / children changed, recombine this node
}

int* longestRepeating(char* s, char* queryCharacters, int* queryIndices,
                      int queryIndicesSize, int* returnSize) {
    int n = strlen(s);                      // 字串長度 / length of the string
    // 線段樹需要 4*n 個節點才夠用 / a segment tree needs up to 4*n nodes to be safe
    Node* tree = (Node*)malloc(sizeof(Node) * 4 * n);  // malloc 動態配置記憶體 / dynamically allocate memory
    build(tree, s, 1, 0, n - 1);            // 從下標 1 當根、負責 [0, n-1] 建樹 / build from root index 1 over [0, n-1]

    int* ans = (int*)malloc(sizeof(int) * queryIndicesSize);  // 存每次查詢答案 / holds each query's answer
    for (int i = 0; i < queryIndicesSize; i++) {              // 依序處理每個查詢 / process queries in order
        update(tree, 1, 0, n - 1, queryIndices[i], queryCharacters[i]);  // 改一個字元 / apply one character change
        ans[i] = tree[1].best;              // 根節點的 best 就是全字串的答案 / root's best is the whole-string answer
    }

    *returnSize = queryIndicesSize;         // 透過指標回傳陣列長度 / report array length via the out-pointer
    free(tree);                             // 釋放線段樹記憶體 / free the segment-tree memory
    return ans;                             // 回傳答案陣列（呼叫端負責釋放）/ return the answer array (caller frees)
}

// 演算法：線段樹，節點記錄最長同字元段與前綴/後綴，合併時處理跨界段。
// Algorithm: segment tree; each node stores the best run plus prefix/suffix so a
// run crossing the split of two children is merged correctly.

class Solution {
    // 每個節點的資訊打包成一個結構 / a struct bundling one node's fields
    struct Node {
        int pref = 0, suf = 0, best = 0, len = 0;  // 前綴/後綴/最佳/長度 / prefix/suffix/best/length
        char lc = 0, rc = 0;                        // 左右端字元 / leftmost & rightmost chars
    };

    vector<Node> tree;   // 用 vector 當線段樹陣列 / a vector as the segment-tree array
    string s;            // 目前的字串狀態 / the current string state

    // 合併左右兩個子節點 / merge two child nodes into their parent
    Node merge(const Node& a, const Node& b) {
        // 若某一子是空段(len==0)，直接回傳另一子 / if a child is empty, return the other
        if (a.len == 0) return b;
        if (b.len == 0) return a;

        Node r;
        r.len = a.len + b.len;               // 長度相加 / lengths add up
        r.lc = a.lc;                         // 左端來自左子 / left end from left child
        r.rc = b.rc;                         // 右端來自右子 / right end from right child

        r.pref = a.pref;                     // 前綴預設是左子前綴 / prefix defaults to left child's
        if (a.pref == a.len && a.rc == b.lc) // 左子整段同字元且邊界相接 / left child all one char and boundary matches
            r.pref = a.len + b.pref;         // 前綴延伸進右子 / extend into right child

        r.suf = b.suf;                       // 後綴預設是右子後綴 / suffix defaults to right child's
        if (b.suf == b.len && b.lc == a.rc)  // 右子整段同字元且邊界相接 / right child all one char and boundary matches
            r.suf = b.len + a.suf;           // 後綴延伸進左子 / extend into left child

        r.best = max(a.best, b.best);        // 先取兩子最佳 / max of children's best
        if (a.rc == b.lc)                    // 邊界字元相同才有跨界段 / crossing run only if boundary chars match
            r.best = max(r.best, a.suf + b.pref);  // 跨界段 = 左後綴 + 右前綴 / crossing = left suffix + right prefix
        return r;
    }

    // 建樹 / build the tree over range [l, r] at array index node
    void build(int node, int l, int r) {
        if (l == r) {                        // 葉子節點 / leaf node
            tree[node] = {1, 1, 1, 1, s[l], s[l]};  // 單字元：各值為 1，兩端同字元 / single char: all 1s, both ends = s[l]
            return;
        }
        int mid = (l + r) / 2;               // 中點 / midpoint
        build(2 * node,     l,     mid);     // 建左半 / build left half
        build(2 * node + 1, mid + 1, r);     // 建右半 / build right half
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);  // 合併 / merge children
    }

    // 單點更新：把 pos 的字元設為 c / point update: set char at pos to c
    void update(int node, int l, int r, int pos, char c) {
        if (l == r) {                        // 目標葉子 / target leaf
            tree[node].lc = tree[node].rc = c;  // 改字元；其餘欄位仍為 1 / change char; other fields stay 1
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2 * node,     l,     mid, pos, c);  // 往左找 / recurse left
        else            update(2 * node + 1, mid + 1, r, pos, c);  // 往右找 / recurse right
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);    // 重新合併 / recombine
    }

public:
    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
        this->s = s;                         // 保存字串到成員 / store the string in the member
        int n = s.size();                    // 字串長度 / string length
        tree.assign(4 * n, Node{});          // 配置 4n 個節點（預設空節點）/ allocate 4n nodes (default-empty)
        build(1, 0, n - 1);                  // 從根(下標1)建樹 / build from root (index 1)

        vector<int> ans;                     // 答案陣列 / the answer array
        ans.reserve(queryIndices.size());    // 預留空間避免多次擴容 / reserve to avoid reallocations
        // range-for：依序取出每個查詢下標 i / range-for over each query index i
        for (int i = 0; i < (int)queryIndices.size(); i++) {
            update(1, 0, n - 1, queryIndices[i], queryCharacters[i]);  // 套用一次修改 / apply one update
            ans.push_back(tree[1].best);     // 根的 best 即答案 / root's best is the answer
        }
        return ans;                          // 回傳結果 / return the results
    }
};