Welcome to Subscribe On Youtube

2213. Longest Substring of One Repeating Character

Description

You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indices queryIndices of length k, both of which are used to describe k queries.

The ith query updates the character in s at index queryIndices[i] to the character queryCharacters[i].

Return an array lengths of length k where lengths[i] is the length of the longest substring of s consisting of only one repeating character after the ith query is performed.

 

Example 1:

Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
Output: [3,3,4]
Explanation: 
- 1st query updates s = "bbbacc". The longest substring consisting of one repeating character is "bbb" with length 3.
- 2nd query updates s = "bbbccc". 
  The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3.
- 3rd query updates s = "bbbbcc". The longest substring consisting of one repeating character is "bbbb" with length 4.
Thus, we return [3,3,4].

Example 2:

Input: s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
Output: [2,3]
Explanation:
- 1st query updates s = "abazz". The longest substring consisting of one repeating character is "zz" with length 2.
- 2nd query updates s = "aaazz". The longest substring consisting of one repeating character is "aaa" with length 3.
Thus, we return [2,3].

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.
  • k == queryCharacters.length == queryIndices.length
  • 1 <= k <= 105
  • queryCharacters consists of lowercase English letters.
  • 0 <= queryIndices[i] < s.length

Solutions

Segment Tree.

  • class Node {
        int l;
        int r;
        int size;
        int lmx;
        int rmx;
        int mx;
        char lc;
        char rc;
    }
    
    class SegmentTree {
        private String s;
        private Node[] tr;
    
        public SegmentTree(String s) {
            int n = s.length();
            this.s = s;
            tr = new Node[n << 2];
            for (int i = 0; i < tr.length; ++i) {
                tr[i] = new Node();
            }
            build(1, 1, n);
        }
    
        public void build(int u, int l, int r) {
            tr[u].l = l;
            tr[u].r = r;
            if (l == r) {
                tr[u].lmx = 1;
                tr[u].rmx = 1;
                tr[u].mx = 1;
                tr[u].size = 1;
                tr[u].lc = s.charAt(l - 1);
                tr[u].rc = s.charAt(l - 1);
                return;
            }
            int mid = (l + r) >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    
        void modify(int u, int x, char v) {
            if (tr[u].l == x && tr[u].r == x) {
                tr[u].lc = v;
                tr[u].rc = v;
                return;
            }
            int mid = (tr[u].l + tr[u].r) >> 1;
            if (x <= mid) {
                modify(u << 1, x, v);
            } else {
                modify(u << 1 | 1, x, v);
            }
            pushup(u);
        }
    
        Node query(int u, int l, int r) {
            if (tr[u].l >= l && tr[u].r <= r) {
                return tr[u];
            }
            int mid = (tr[u].l + tr[u].r) >> 1;
            if (r <= mid) {
                return query(u << 1, l, r);
            }
            if (l > mid) {
                return query(u << 1 | 1, l, r);
            }
            Node ans = new Node();
            Node left = query(u << 1, l, r);
            Node right = query(u << 1 | 1, l, r);
            pushup(ans, left, right);
            return ans;
        }
    
        void pushup(Node root, Node left, Node right) {
            root.lc = left.lc;
            root.rc = right.rc;
            root.size = left.size + right.size;
    
            root.mx = Math.max(left.mx, right.mx);
            root.lmx = left.lmx;
            root.rmx = right.rmx;
    
            if (left.rc == right.lc) {
                if (left.lmx == left.size) {
                    root.lmx += right.lmx;
                }
                if (right.rmx == right.size) {
                    root.rmx += left.rmx;
                }
                root.mx = Math.max(root.mx, left.rmx + right.lmx);
            }
        }
    
        void pushup(int u) {
            pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
        }
    }
    
    class Solution {
        public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
            SegmentTree tree = new SegmentTree(s);
            int k = queryCharacters.length();
            int[] ans = new int[k];
            for (int i = 0; i < k; ++i) {
                int x = queryIndices[i] + 1;
                char c = queryCharacters.charAt(i);
                tree.modify(1, x, c);
                ans[i] = tree.query(1, 1, s.length()).mx;
            }
            return ans;
        }
    }
    
  • class Node {
    public:
        int l, r, size, lmx, rmx, mx;
        char lc, rc;
    };
    
    class SegmentTree {
    private:
        string s;
        vector<Node*> tr;
    
    public:
        SegmentTree(string& s) {
            this->s = s;
            int n = s.size();
            tr.resize(n << 2);
            for (int i = 0; i < tr.size(); ++i) tr[i] = new Node();
            build(1, 1, n);
        }
    
        void build(int u, int l, int r) {
            tr[u]->l = l;
            tr[u]->r = r;
            if (l == r) {
                tr[u]->lmx = tr[u]->rmx = tr[u]->mx = tr[u]->size = 1;
                tr[u]->lc = tr[u]->rc = s[l - 1];
                return;
            }
            int mid = (l + r) >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    
        void modify(int u, int x, char v) {
            if (tr[u]->l == x && tr[u]->r == x) {
                tr[u]->lc = tr[u]->rc = v;
                return;
            }
            int mid = (tr[u]->l + tr[u]->r) >> 1;
            if (x <= mid)
                modify(u << 1, x, v);
            else
                modify(u << 1 | 1, x, v);
            pushup(u);
        }
    
        Node* query(int u, int l, int r) {
            if (tr[u]->l >= l && tr[u]->r <= r) return tr[u];
            int mid = (tr[u]->l + tr[u]->r) >> 1;
            if (r <= mid) return query(u << 1, l, r);
            if (l > mid) query(u << 1 | 1, l, r);
            Node* ans = new Node();
            Node* left = query(u << 1, l, r);
            Node* right = query(u << 1 | 1, l, r);
            pushup(ans, left, right);
            return ans;
        }
    
        void pushup(Node* root, Node* left, Node* right) {
            root->lc = left->lc;
            root->rc = right->rc;
            root->size = left->size + right->size;
    
            root->mx = max(left->mx, right->mx);
            root->lmx = left->lmx;
            root->rmx = right->rmx;
    
            if (left->rc == right->lc) {
                if (left->lmx == left->size) root->lmx += right->lmx;
                if (right->rmx == right->size) root->rmx += left->rmx;
                root->mx = max(root->mx, left->rmx + right->lmx);
            }
        }
    
        void pushup(int u) {
            pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
        }
    };
    
    class Solution {
    public:
        vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
            SegmentTree* tree = new SegmentTree(s);
            int k = queryCharacters.size();
            vector<int> ans(k);
            for (int i = 0; i < k; ++i) {
                int x = queryIndices[i] + 1;
                tree->modify(1, x, queryCharacters[i]);
                ans[i] = tree->query(1, 1, s.size())->mx;
            }
            return ans;
        }
    };
    
  • class Node:
        def __init__(self):
            self.l = 0
            self.r = 0
            self.lmx = 0
            self.rmx = 0
            self.mx = 0
            self.size = 0
            self.lc = None
            self.rc = None
    
    
    N = 100010
    tr = [Node() for _ in range(N << 2)]
    
    
    class SegmentTree:
        def __init__(self, s):
            n = len(s)
            self.s = s
            self.build(1, 1, n)
    
        def build(self, u, l, r):
            tr[u].l = l
            tr[u].r = r
            if l == r:
                tr[u].lmx = tr[u].rmx = tr[u].mx = tr[u].size = 1
                tr[u].lc = tr[u].rc = self.s[l - 1]
                return
            mid = (l + r) >> 1
            self.build(u << 1, l, mid)
            self.build(u << 1 | 1, mid + 1, r)
            self.pushup(u)
    
        def modify(self, u, x, v):
            if tr[u].l == x and tr[u].r == x:
                tr[u].lc = tr[u].rc = v
                return
            mid = (tr[u].l + tr[u].r) >> 1
            if x <= mid:
                self.modify(u << 1, x, v)
            else:
                self.modify(u << 1 | 1, x, v)
            self.pushup(u)
    
        def query(self, u, l, r):
            if tr[u].l >= l and tr[u].r <= r:
                return tr[u]
            mid = (tr[u].l + tr[u].r) >> 1
            if r <= mid:
                return self.query(u << 1, l, r)
            if l > mid:
                return self.query(u << 1 | 1, l, r)
            left, right = self.query(u << 1, l, r), self.query(u << 1 | 1, l, r)
            ans = Node()
            self._pushup(ans, left, right)
            return ans
    
        def _pushup(self, root, left, right):
            root.lc, root.rc = left.lc, right.rc
            root.size = left.size + right.size
    
            root.mx = max(left.mx, right.mx)
            root.lmx, root.rmx = left.lmx, right.rmx
    
            if left.rc == right.lc:
                if left.lmx == left.size:
                    root.lmx += right.lmx
                if right.rmx == right.size:
                    root.rmx += left.rmx
                root.mx = max(root.mx, left.rmx + right.lmx)
    
        def pushup(self, u):
            self._pushup(tr[u], tr[u << 1], tr[u << 1 | 1])
    
    
    class Solution:
        def longestRepeating(
            self, s: str, queryCharacters: str, queryIndices: List[int]
        ) -> List[int]:
            tree = SegmentTree(s)
            k = len(queryIndices)
            ans = []
            for i, c in enumerate(queryCharacters):
                x = queryIndices[i] + 1
                tree.modify(1, x, c)
                ans.append(tree.query(1, 1, len(s)).mx)
            return ans
    
    
  • type segmentTree struct {
    	str []byte
    	mx  []int
    	lmx []int
    	rmx []int
    }
    
    func newSegmentTree(s string) *segmentTree {
    	n := len(s)
    	t := &segmentTree{
    		str: []byte(s),
    		mx:  make([]int, n<<2),
    		lmx: make([]int, n<<2),
    		rmx: make([]int, n<<2),
    	}
    	t.build(0, 0, n-1)
    	return t
    }
    
    func (t *segmentTree) build(x, l, r int) {
    	if l == r {
    		t.lmx[x] = 1
    		t.rmx[x] = 1
    		t.mx[x] = 1
    		return
    	}
    	m := int(uint(l+r) >> 1)
    	t.build(x*2+1, l, m)
    	t.build(x*2+2, m+1, r)
    	t.pushup(x, l, m, r)
    }
    
    func (t *segmentTree) pushup(x, l, m, r int) {
    	lch, rch := x*2+1, x*2+2
    	t.lmx[x] = t.lmx[lch]
    	t.rmx[x] = t.rmx[rch]
    	t.mx[x] = max(t.mx[lch], t.mx[rch])
    	// can be merged
    	if t.str[m] == t.str[m+1] {
    		if t.lmx[lch] == m-l+1 {
    			t.lmx[x] += t.lmx[rch]
    		}
    		if t.rmx[rch] == r-m {
    			t.rmx[x] += t.rmx[lch]
    		}
    		t.mx[x] = max(t.mx[x], t.rmx[lch]+t.lmx[rch])
    	}
    }
    
    func (t *segmentTree) update(x, l, r, pos int, val byte) {
    	if l == r {
    		t.str[pos] = val
    		return
    	}
    	m := int(uint(l+r) >> 1)
    	if pos <= m {
    		t.update(x*2+1, l, m, pos, val)
    	} else {
    		t.update(x*2+2, m+1, r, pos, val)
    	}
    	t.pushup(x, l, m, r)
    }
    
    func longestRepeating(s string, queryCharacters string, queryIndices []int) []int {
    	ans := make([]int, len(queryCharacters))
    	t := newSegmentTree(s)
    	n := len(s)
    	for i, c := range queryCharacters {
    		t.update(0, 0, n-1, queryIndices[i], byte(c))
    		ans[i] = t.mx[0]
    	}
    	return ans
    }
    
  • class Node {
        l: number;
        r: number;
        lmx: number;
        rmx: number;
        mx: number;
    
        constructor(l: number, r: number) {
            this.l = l;
            this.r = r;
            this.lmx = 1;
            this.rmx = 1;
            this.mx = 1;
        }
    }
    
    class SegmentTree {
        private s: string[];
        private tr: Node[];
    
        constructor(s: string) {
            this.s = s.split('');
            this.tr = Array(s.length * 4)
                .fill(null)
                .map(() => new Node(0, 0));
            this.build(1, 1, s.length);
        }
    
        private build(u: number, l: number, r: number): void {
            this.tr[u] = new Node(l, r);
            if (l === r) {
                return;
            }
            const mid = (l + r) >> 1;
            this.build(u << 1, l, mid);
            this.build((u << 1) | 1, mid + 1, r);
            this.pushup(u);
        }
    
        public modify(u: number, x: number, v: string): void {
            if (this.tr[u].l === x && this.tr[u].r === x) {
                this.s[x - 1] = v;
                return;
            }
            const mid = (this.tr[u].l + this.tr[u].r) >> 1;
            if (x <= mid) {
                this.modify(u << 1, x, v);
            } else {
                this.modify((u << 1) | 1, x, v);
            }
            this.pushup(u);
        }
    
        public query(u: number, l: number, r: number): number {
            if (this.tr[u].l >= l && this.tr[u].r <= r) {
                return this.tr[u].mx;
            }
            const mid = (this.tr[u].l + this.tr[u].r) >> 1;
            let ans = 0;
            if (r <= mid) {
                ans = this.query(u << 1, l, r);
            } else if (l > mid) {
                ans = Math.max(ans, this.query((u << 1) | 1, l, r));
            } else {
                ans = Math.max(this.query(u << 1, l, r), this.query((u << 1) | 1, l, r));
            }
            return ans;
        }
    
        private pushup(u: number): void {
            const root = this.tr[u];
            const left = this.tr[u << 1];
            const right = this.tr[(u << 1) | 1];
            root.mx = Math.max(left.mx, right.mx);
            root.lmx = left.lmx;
            root.rmx = right.rmx;
            const a = left.r - left.l + 1;
            const b = right.r - right.l + 1;
            if (this.s[left.r - 1] === this.s[right.l - 1]) {
                if (left.lmx === a) {
                    root.lmx += right.lmx;
                }
                if (right.rmx === b) {
                    root.rmx += left.rmx;
                }
                root.mx = Math.max(root.mx, left.rmx + right.lmx);
            }
        }
    }
    
    function longestRepeating(s: string, queryCharacters: string, queryIndices: number[]): number[] {
        const tree = new SegmentTree(s);
        const k = queryIndices.length;
        const ans: number[] = new Array(k);
        const n = s.length;
        for (let i = 0; i < k; ++i) {
            const x = queryIndices[i] + 1;
            const v = queryCharacters[i];
            tree.modify(1, x, v);
            ans[i] = tree.query(1, 1, n);
        }
        return ans;
    }
    
    

All Problems

All Solutions