【綜合筆試題】難度 4/5，字元處理的線段樹經典運用

題目描述

這是 LeetCode 上的 ​​2213. 由單個字元重複的最長子字元串​​ ，難度為 困難。

Tag : 「區間求和」、「線段樹」

給你一個下标從 開始的字元串 ​​

​s​

​​ 。另給你一個下标從 開始、長度為 的字元串 ​​

​queryCharacters​

​​，一個下标從 開始、長度也是 的整數 下标 數組 ​​

​queryIndices​

​​，這兩個都用來描述

第 個查詢會将 ​​

​s​

​​ 中位于下标 的字元更新為 。

傳回一個長度為 的數組 ​​

​lengths​

​​，其中 是在執行第 個查詢之後 ​​

​s​

​ 中僅由單個字元重複組成的 最長子字元串的長度 。

示例 1：

輸入：s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]

輸出：[3,3,4]

解釋：
- 第 1 次查詢更新後 s = "bbbacc" 。由單個字元重複組成的最長子字元串是 "bbb" ，長度為 3 。
- 第 2 次查詢更新後 s = "bbbccc" 。由單個字元重複組成的最長子字元串是 "bbb" 或 "ccc"，長度為 3 。
- 第 3 次查詢更新後 s = "bbbbcc" 。由單個字元重複組成的最長子字元串是 "bbbb" ，長度為 4 。
是以，傳回 [3,3,4]      

示例 2：

輸入：s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]

輸出：[2,3]

解釋：
- 第 1 次查詢更新後 s = "abazz" 。由單個字元重複組成的最長子字元串是 "zz" ，長度為 2 。
- 第 2 次查詢更新後 s = "aaazz" 。由單個字元重複組成的最長子字元串是 "aaa" ，長度為 3 。
是以，傳回 [2,3]      

提示：

• ​

  ​s​

  ​ 由小寫英文字母組成
• ​

  ​queryCharacters​

  ​ 由小寫英文字母組成

線段樹

這是一道經典的線段樹應用題。

根據題意，涉及的操作 “似乎” 是「單點修改」和「區間查詢」，那麼根據 ​​(題解) 307. 區域和檢索 - 數組可修改​​ 的總結，我們應該使用的是「樹狀數組」嗎？

其實并不是（或者說不能直接是），原因在于我們查詢的是「修改過後 ​

​s​

​ 中相同字元連續段的最大長度」，而當我們進行所謂的「單點修改」時，會導緻原本的連續段被破壞，或者形成新的連續段。也就是此處的修改對于結果而言，并不是單點的。

使用線段樹求解，我們唯一需要考慮的是：在 ​

​Node​

​ 中維護些什麼資訊？

對于線段樹的節點資訊設計，通常會包含基本的左右端點 ​

​l​

​​、​

​r​

​​ 以及查詢目标值 ​

​val​

​​ ，然後再考慮維護 ​

​val​

​ 還需要一些什麼輔助資訊。

對于本題，我們還需要額外維護 ​

​prefix​

​​ 和 ​

​suffix​

​​，分别代表「目前區間 内字首相同字元連續段的最大長度」和「目前區間

然後考慮每次修改，如何使用子節點資訊更新父節點（​

​pushup​

​ 操作）：

• 對于一般性的合并（目前節點的兩個子節點的銜接點不是相同字元）而言：

• ​

  ​tr[u].prefix = tr[u << 1].prefix​

  ​：目前父節點（區間）的字首最大長度等于左子節點（區間）的字首最大長度；
• ​

  ​tr[u].suffix = tr[u << 1 | 1].suffix​

  ​：目前父節點（區間）的字尾最大長度等于右子節點（區間）的字尾最大長度；
• ​

  ​tr[u].val = max(left.val, right.val)​

  ​：目前父節點（區間）的最大長度為兩子節點（區間）的最大長度。

• 對于非一般性的合并（目前節點的兩個子節點的銜接點為相同字元）：

• ​

  ​tr[u].val = max(tr[u].val, left.suffix + right.prefix)​

  ​：首先可以确定的是「左區間的字尾」和「右區間的字首」可以拼接在一起，是以可以使用拼接長度來嘗試更新目前節點的最大值；
• ​

  ​tr[u].suffix = bLen + left.suffix​

  ​​：其中​

  ​bLen​

  ​​ 為右節點（區間）的長度。當且僅當右節點（區間）整一段都是相同字元時（即滿足​

  ​right.prefix = right.suffix = bLen​

  ​​），可以使用​

  ​bLen + left.suffix​

  ​​ 來更新​

  ​tr[u].suffix​

  ​；
• ​

  ​tr[u].prefix = aLen + right.prefix​

  ​​：其中​

  ​aLen​

  ​​ 為左節點（區間）的長度。當且僅當左節點（區間）整一段都是相同字元時（即滿足​

  ​left.prefix = left.prefix = aLen​

  ​​），可以使用​

  ​aLen + right.prefix​

  ​​ 來更新​

  ​tr[u].prefix ​

  ​。

代碼：

class Solution {
    class Node {
        int l, r, prefix, suffix, val;
        Node(int _l, int _r) {
            l = _l; r = _r;
            prefix = suffix = val = 1;
        }
    }
    char[] cs;
    Node[] tr;
    void build(int u, int l, int {
        tr[u] = new Node(l, r);
        if (l == r) return ;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void update(int u, int x, char {
        if (tr[u].l == x && tr[u].r == x) {
            cs[x - 1] = c;
            return ;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) update(u << 1, x, c);
        else update(u << 1 | 1, x, c);
        pushup(u);
    }
    int query(int u, int l, int {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
        int ans = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) ans = query(u << 1, l, r);
        if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r));
        return ans;
    }
    void pushup(int {
        Node left = tr[u << 1], right = tr[u << 1 | 1];
        int aLen = left.r - left.l + 1, bLen = right.r - right.l + 1;
        char ac = cs[left.r - 1], bc = cs[right.l - 1];
        tr[u].prefix = left.prefix; tr[u].suffix = right.suffix;
        tr[u].val = Math.max(left.val, right.val);
        if (ac == bc) {
            if (left.prefix == aLen) tr[u].prefix = aLen + right.prefix;
            if (right.prefix == bLen) tr[u].suffix = bLen + left.suffix;
            tr[u].val = Math.max(tr[u].val, left.suffix + right.prefix);
        }
    }
    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
        cs = s.toCharArray();
        int n = cs.length, m = queryCharacters.length();
        tr = new Node[n * 4];
        build(1, 1, n);
        for (int i = 0; i < n; i++) update(1, i + 1, cs[i]);
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            update(1, queryIndices[i] + 1, queryCharacters.charAt(i));
            ans[i] = query(1, 1, n);
        }
        return      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.2213​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。