[comprehensive pen test] difficulty 4/5, classic application of line segment tree for character processing

Title Description

This is a LeetCode Upper 2213. The longest substring repeated by a single character , The difficulty is difficult .

Tag : 「 Sum of intervals 」、「 Line segment tree 」

I'll give you a subscript from Starting string s . Give you another subscript from Start 、 The length is String queryCharacters, A subscript from Start 、 The length is also The integer of Subscript Array  queryIndices, Both are used to describe A query .

The first A query will s In the subscript The character of is updated to .

Returns a length of Array of lengths, among It's in execution After two queries s Consisting only of single character repetitions The length of the longest substring .

Example 1：

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

 Output ：[3,3,4]

 explain ：
-  The first  1  After the first query update  s = "bbbacc" . The longest substring consisting of a single character repetition is  "bbb" , The length is  3 .
-  The first  2  After the first query update  s = "bbbccc" . The longest substring consisting of a single character repetition is  "bbb"  or  "ccc", The length is  3 .
-  The first  3  After the first query update  s = "bbbbcc" . The longest substring consisting of a single character repetition is  "bbbb" , The length is  4 .
 therefore , return  [3,3,4] .

Example 2：

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

 Output ：[2,3]

 explain ：
-  The first  1  After the first query update  s = "abazz" . The longest substring consisting of a single character repetition is  "zz" , The length is  2 .
-  The first  2  After the first query update  s = "aaazz" . The longest substring consisting of a single character repetition is  "aaa" , The length is  3 .
 therefore , return  [2,3] .

Tips ：

• s It's made up of lowercase letters
• queryCharacters It's made up of lowercase letters

Line segment tree

This is a classic line segment tree application problem .

According to the meaning , Operations involved “ Seems to be ” yes 「 Single point modification 」 and 「 Interval query 」, So according to ( Answer key ) 307. Area and retrieval - Array can be modified Summary of , What we should use is 「 Tree array 」 Do you ？

It's not （ Or not directly ）, The reason is that we are inquiring about 「 After the modification s The maximum length of consecutive segments of the same character in 」, And when we do what we call 「 Single point modification 」 when , It will cause the original continuous section to be destroyed , Or form new continuous segments . That is, the modification here is for the result , It's not a single point .

Use the segment tree to solve , The only thing we need to consider is ： stay Node What information is maintained in ？

For the node information design of line segment tree , It usually contains basic left and right endpoints l、r And query the target value val , Then consider maintenance val What additional information is needed .

For this question , We need additional maintenance prefix and suffix, Represent the 「 Current interval The maximum length of consecutive segments with the same character as the inner prefix 」 and 「 Current interval The maximum length of consecutive segments with the same character suffix 」.

Then consider each modification , How to update parent node with child node information （pushup operation ）：

• For general mergers （ The connection points of the two child nodes of the current node are not the same characters ） for ：

  • tr[u].prefix = tr[u << 1].prefix： Current parent node （ Section ） The maximum length of the prefix is equal to the left child node （ Section ） The maximum prefix length of ;
  • tr[u].suffix = tr[u << 1 | 1].suffix： Current parent node （ Section ） The maximum length of the suffix is equal to the right child node （ Section ） The maximum length of the suffix ;
  • tr[u].val = max(left.val, right.val)： Current parent node （ Section ） The maximum length of is two child nodes （ Section ） Maximum length of .

• For non general mergers （ The connection point of the two child nodes of the current node is the same character ）：

  • tr[u].val = max(tr[u].val, left.suffix + right.prefix)： The first thing to be sure of is 「 Suffix of left interval 」 and 「 Prefix of right interval 」 Can be spliced together , Therefore, you can use the splice length to try to update the maximum value of the current node ;
  • tr[u].suffix = bLen + left.suffix： among bLen For the right node （ Section ） The length of . If and only if the right node （ Section ） When the whole paragraph is the same character （ The meet right.prefix = right.suffix = bLen）, have access to bLen + left.suffix To update tr[u].suffix;
  • tr[u].prefix = aLen + right.prefix： among aLen For the left node （ Section ） The length of . If and only if the left node （ Section ） When the whole paragraph is the same character （ The meet left.prefix = left.prefix = aLen）, have access to aLen + right.prefix To update tr[u].prefix .

Code ：

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 r) {
    
        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 c) {
    
        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 r) {
    
        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 u) {
    
        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 ans;
    }
}

• Time complexity ：
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.2213 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases

This paper is written by mdnice Multi platform Publishing