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 indicesqueryIndices 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 arraylengthsof length k wherelengths[i]is the length of the longest substring of s consisting of only one repeating character after theithquery 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.
typesegmentTreestruct{str[]bytemx[]intlmx[]intrmx[]int}funcnewSegmentTree(sstring)*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)returnt}func(t*segmentTree)build(x,l,rint){ifl==r{t.lmx[x]=1t.rmx[x]=1t.mx[x]=1return}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,rint){lch,rch:=x*2+1,x*2+2t.lmx[x]=t.lmx[lch]t.rmx[x]=t.rmx[rch]t.mx[x]=max(t.mx[lch],t.mx[rch])// can be mergedift.str[m]==t.str[m+1]{ift.lmx[lch]==m-l+1{t.lmx[x]+=t.lmx[rch]}ift.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,posint,valbyte){ifl==r{t.str[pos]=valreturn}m:=int(uint(l+r)>>1)ifpos<=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)}funclongestRepeating(sstring,queryCharactersstring,queryIndices[]int)[]int{ans:=make([]int,len(queryCharacters))t:=newSegmentTree(s)n:=len(s)fori,c:=rangequeryCharacters{t.update(0,0,n-1,queryIndices[i],byte(c))ans[i]=t.mx[0]}returnans}