2213. Longest Substring of One Repeating Character

class Solution {
    private char[] leftCh, rightCh;
    private int[] pre, suf, best;

    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
        int n = s.length();
        leftCh = new char[4 * n];
        rightCh = new char[4 * n];
        pre = new int[4 * n];
        suf = new int[4 * n];
        best = new int[4 * n];

        build(1, 0, n - 1, s);

        int k = queryCharacters.length();
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            update(1, 0, n - 1, queryIndices[i], queryCharacters.charAt(i));
            ans[i] = best[1];
        }

        return ans;
    }

    private void build(int node, int l, int r, String s) {
        if (l == r) {
            leftCh[node] = rightCh[node] = s.charAt(l);
            pre[node] = suf[node] = best[node] = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(2 * node, l, mid, s);
        build(2 * node + 1, mid + 1, r, s);
        pull(node, l, mid, r);
    }

    private void update(int node, int l, int r, int idx, char c) {
        if (l == r) {
            leftCh[node] = rightCh[node] = c;
            pre[node] = suf[node] = best[node] = 1;
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) {
            update(2 * node, l, mid, idx, c);
        } else {
            update(2 * node + 1, mid + 1, r, idx, c);
        }
        pull(node, l, mid, r);
    }

    private void pull(int node, int l, int mid, int r) {
        int leftNode = 2 * node, rightNode = 2 * node + 1;
        int leftLen = mid - l + 1;
        int rightLen = r - mid;

        leftCh[node] = leftCh[leftNode];
        rightCh[node] = rightCh[rightNode];

        pre[node] = pre[leftNode];
        if (pre[leftNode] == leftLen && rightCh[leftNode] == leftCh[rightNode]) {
            pre[node] += pre[rightNode];
        }

        suf[node] = suf[rightNode];
        if (suf[rightNode] == rightLen && rightCh[leftNode] == leftCh[rightNode]) {
            suf[node] += suf[leftNode];
        }

        best[node] = Math.max(best[leftNode], best[rightNode]);
        if (rightCh[leftNode] == leftCh[rightNode]) {
            best[node] = Math.max(best[node], suf[leftNode] + pre[rightNode]);
        }
    }
}

class Solution:
    def longestRepeating(self, s, queryCharacters, queryIndices):
        n = len(s)

        left_ch = [''] * (4 * n)
        right_ch = [''] * (4 * n)
        pre = [0] * (4 * n)
        suf = [0] * (4 * n)
        best = [0] * (4 * n)

        def pull(node, l, mid, r):
            left_node = 2 * node
            right_node = 2 * node + 1

            left_len = mid - l + 1
            right_len = r - mid

            left_ch[node] = left_ch[left_node]
            right_ch[node] = right_ch[right_node]

            pre[node] = pre[left_node]

            if (pre[left_node] == left_len and
                    right_ch[left_node] == left_ch[right_node]):
                pre[node] += pre[right_node]

            suf[node] = suf[right_node]

            if (suf[right_node] == right_len and
                    right_ch[left_node] == left_ch[right_node]):
                suf[node] += suf[left_node]

            best[node] = max(best[left_node], best[right_node])

            if right_ch[left_node] == left_ch[right_node]:
                best[node] = max(
                    best[node],
                    suf[left_node] + pre[right_node]
                )

        def build(node, l, r):
            if l == r:
                left_ch[node] = right_ch[node] = s[l]
                pre[node] = suf[node] = best[node] = 1
                return

            mid = (l + r) // 2

            build(2 * node, l, mid)
            build(2 * node + 1, mid + 1, r)

            pull(node, l, mid, r)

        def update(node, l, r, idx, c):
            if l == r:
                left_ch[node] = right_ch[node] = c
                pre[node] = suf[node] = best[node] = 1
                return

            mid = (l + r) // 2

            if idx <= mid:
                update(2 * node, l, mid, idx, c)
            else:
                update(2 * node + 1, mid + 1, r, idx, c)

            pull(node, l, mid, r)

        build(1, 0, n - 1,)

        ans = []

        for i in range(len(queryCharacters)):
            update(
                1,
                0,
                n - 1,
                queryIndices[i],
                queryCharacters[i]
            )

            ans.append(best[1])

        return ans

class Solution {
private:
    vector<char> leftCh, rightCh;
    vector<int> pre, suf, best;

    void pull(int node, int l, int mid, int r) {
        int leftNode = 2 * node;
        int rightNode = 2 * node + 1;

        int leftLen = mid - l + 1;
        int rightLen = r - mid;

        leftCh[node] = leftCh[leftNode];
        rightCh[node] = rightCh[rightNode];

        pre[node] = pre[leftNode];

        if (pre[leftNode] == leftLen &&
            rightCh[leftNode] == leftCh[rightNode]) {
            pre[node] += pre[rightNode];
        }

        suf[node] = suf[rightNode];

        if (suf[rightNode] == rightLen &&
            rightCh[leftNode] == leftCh[rightNode]) {
            suf[node] += suf[leftNode];
        }

        best[node] = max(best[leftNode], best[rightNode]);

        if (rightCh[leftNode] == leftCh[rightNode]) {
            best[node] = max(
                best[node],
                suf[leftNode] + pre[rightNode]
            );
        }
    }

    void build(int node, int l, int r, const string& s) {
        if (l == r) {
            leftCh[node] = rightCh[node] = s[l];
            pre[node] = suf[node] = best[node] = 1;
            return;
        }

        int mid = (l + r) / 2;

        build(2 * node, l, mid, s);
        build(2 * node + 1, mid + 1, r, s);

        pull(node, l, mid, r);
    }

    void update(int node, int l, int r, int idx, char c) {
        if (l == r) {
            leftCh[node] = rightCh[node] = c;
            pre[node] = suf[node] = best[node] = 1;
            return;
        }

        int mid = (l + r) / 2;

        if (idx <= mid) {
            update(2 * node, l, mid, idx, c);
        } else {
            update(2 * node + 1, mid + 1, r, idx, c);
        }

        pull(node, l, mid, r);
    }

public:
    vector<int> longestRepeating(
        string s,
        string queryCharacters,
        vector<int>& queryIndices
    ) {
        int n = s.length();

        leftCh.resize(4 * n);
        rightCh.resize(4 * n);
        pre.assign(4 * n, 0);
        suf.assign(4 * n, 0);
        best.assign(4 * n, 0);

        build(1, 0, n - 1, s);

        vector<int> ans;

        for (int i = 0; i < queryCharacters.length(); i++) {
            update(
                1,
                0,
                n - 1,
                queryIndices[i],
                queryCharacters[i]
            );

            ans.push_back(best[1]);
        }

        return ans;
    }
};

var longestRepeating = function(s, queryCharacters, queryIndices) {
    const n = s.length;

    const leftCh = new Array(4 * n);
    const rightCh = new Array(4 * n);
    const pre = new Array(4 * n).fill(0);
    const suf = new Array(4 * n).fill(0);
    const best = new Array(4 * n).fill(0);

    function pull(node, l, mid, r) {
        const leftNode = 2 * node;
        const rightNode = 2 * node + 1;

        const leftLen = mid - l + 1;
        const rightLen = r - mid;

        leftCh[node] = leftCh[leftNode];
        rightCh[node] = rightCh[rightNode];

        pre[node] = pre[leftNode];

        if (
            pre[leftNode] === leftLen &&
            rightCh[leftNode] === leftCh[rightNode]
        ) {
            pre[node] += pre[rightNode];
        }

        suf[node] = suf[rightNode];

        if (
            suf[rightNode] === rightLen &&
            rightCh[leftNode] === leftCh[rightNode]
        ) {
            suf[node] += suf[leftNode];
        }

        best[node] = Math.max(
            best[leftNode],
            best[rightNode]
        );

        if (rightCh[leftNode] === leftCh[rightNode]) {
            best[node] = Math.max(
                best[node],
                suf[leftNode] + pre[rightNode]
            );
        }
    }

    function build(node, l, r) {
        if (l === r) {
            leftCh[node] = rightCh[node] = s[l];
            pre[node] = suf[node] = best[node] = 1;
            return;
        }

        const mid = Math.floor((l + r) / 2);

        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);

        pull(node, l, mid, r);
    }

    function update(node, l, r, idx, c) {
        if (l === r) {
            leftCh[node] = rightCh[node] = c;
            pre[node] = suf[node] = best[node] = 1;
            return;
        }

        const mid = Math.floor((l + r) / 2);

        if (idx <= mid) {
            update(2 * node, l, mid, idx, c);
        } else {
            update(2 * node + 1, mid + 1, r, idx, c);
        }

        pull(node, l, mid, r);
    }

    build(1, 0, n - 1);

    const ans = [];

    for (let i = 0; i < queryCharacters.length; i++) {
        update(
            1,
            0,
            n - 1,
            queryIndices[i],
            queryCharacters[i]
        );

        ans.push(best[1]);
    }

    return ans;
};