|
1 | 1 | packageg2201_2300.s2213_longest_substring_of_one_repeating_character; |
2 | 2 |
|
3 | 3 | // #Hard #Array #String #Ordered_Set #Segment_Tree |
4 | | -// #2022_06_12_Time_141_ms_(86.81%)_Space_148.3_MB_(47.22%) |
| 4 | +// #2025_03_25_Time_79_ms_(89.74%)_Space_66.05_MB_(89.74%) |
5 | 5 |
|
6 | 6 | publicclassSolution { |
7 | | -staticclassTreeNode { |
8 | | -intstart; |
9 | | -intend; |
10 | | -charleftChar; |
11 | | -intleftCharLen; |
12 | | -charrightChar; |
13 | | -intrightCharLen; |
14 | | -intmax; |
15 | | -TreeNodeleft; |
16 | | -TreeNoderight; |
17 | | - |
18 | | -TreeNode(intstart,intend) { |
19 | | -this.start =start; |
20 | | -this.end =end; |
21 | | -left =null; |
22 | | -right =null; |
23 | | - } |
24 | | - } |
| 7 | +privatechar[]ca; |
25 | 8 |
|
26 | 9 | publicint[]longestRepeating(Strings,StringqueryCharacters,int[]queryIndices) { |
27 | | -char[]sChar =s.toCharArray(); |
28 | | -char[]qChar =queryCharacters.toCharArray(); |
29 | | -TreeNoderoot =buildTree(sChar,0,sChar.length -1); |
30 | | -int[]result =newint[qChar.length]; |
31 | | -for (inti =0;i <qChar.length;i++) { |
32 | | -updateTree(root,queryIndices[i],qChar[i]); |
33 | | -if (root !=null) { |
34 | | -result[i] =root.max; |
35 | | - } |
| 10 | +ca =s.toCharArray(); |
| 11 | +int[]result =newint[queryIndices.length]; |
| 12 | +SegmentTreeroot =newSegmentTree(0,ca.length); |
| 13 | +for (inti =0;i <queryIndices.length;i++) { |
| 14 | +ca[queryIndices[i]] =queryCharacters.charAt(i); |
| 15 | +root.update(queryIndices[i]); |
| 16 | +result[i] =root.longest; |
36 | 17 | } |
37 | 18 | returnresult; |
38 | 19 | } |
39 | 20 |
|
40 | | -privateTreeNodebuildTree(char[]s,intfrom,intto) { |
41 | | -if (from >to) { |
42 | | -returnnull; |
43 | | - } |
44 | | -TreeNoderoot =newTreeNode(from,to); |
45 | | -if (from ==to) { |
46 | | -root.max =1; |
47 | | -root.rightChar =root.leftChar =s[from]; |
48 | | -root.leftCharLen =root.rightCharLen =1; |
49 | | -returnroot; |
50 | | - } |
51 | | -intmiddle =from + (to -from) /2; |
52 | | -root.left =buildTree(s,from,middle); |
53 | | -root.right =buildTree(s,middle +1,to); |
54 | | -updateNode(root); |
55 | | -returnroot; |
56 | | - } |
| 21 | +privateclassSegmentTree { |
| 22 | +finalintstart; |
| 23 | +finalintend; |
| 24 | +intlongest; |
| 25 | +intleftLength; |
| 26 | +intrightLength; |
| 27 | +SegmentTreeleft; |
| 28 | +SegmentTreeright; |
57 | 29 |
|
58 | | -privatevoidupdateTree(TreeNoderoot,intindex,charc) { |
59 | | -if (root ==null ||root.start >index ||root.end <index) { |
60 | | -return; |
61 | | - } |
62 | | -if (root.start ==index &&root.end ==index) { |
63 | | -root.leftChar =root.rightChar =c; |
64 | | -return; |
| 30 | +SegmentTree(intstart,intend) { |
| 31 | +this.start =start; |
| 32 | +this.end =end; |
| 33 | +if (end -start >1) { |
| 34 | +intmid = (start +end) /2; |
| 35 | +left =newSegmentTree(start,mid); |
| 36 | +right =newSegmentTree(mid,end); |
| 37 | +merge(); |
| 38 | + }else { |
| 39 | +longest =leftLength =rightLength =1; |
| 40 | + } |
65 | 41 | } |
66 | | -updateTree(root.left,index,c); |
67 | | -updateTree(root.right,index,c); |
68 | | -updateNode(root); |
69 | | - } |
70 | 42 |
|
71 | | -privatevoidupdateNode(TreeNoderoot) { |
72 | | -if (root ==null) { |
73 | | -return; |
74 | | - } |
75 | | -root.leftChar =root.left.leftChar; |
76 | | -root.leftCharLen =root.left.leftCharLen; |
77 | | -root.rightChar =root.right.rightChar; |
78 | | -root.rightCharLen =root.right.rightCharLen; |
79 | | -root.max =Math.max(root.left.max,root.right.max); |
80 | | -if (root.left.rightChar ==root.right.leftChar) { |
81 | | -intlen =root.left.rightCharLen +root.right.leftCharLen; |
82 | | -if (root.left.leftChar ==root.left.rightChar |
83 | | - &&root.left.leftCharLen ==root.left.end -root.left.start +1) { |
84 | | -root.leftCharLen =len; |
| 43 | +voidupdate(intindex) { |
| 44 | +if (end -start ==1) { |
| 45 | +return; |
| 46 | + } |
| 47 | +if (index <left.end) { |
| 48 | +left.update(index); |
| 49 | + }else { |
| 50 | +right.update(index); |
85 | 51 | } |
86 | | -if (root.right.leftChar ==root.right.rightChar |
87 | | - &&root.right.leftCharLen ==root.right.end -root.right.start +1) { |
88 | | -root.rightCharLen =len; |
| 52 | +merge(); |
| 53 | + } |
| 54 | + |
| 55 | +privatevoidmerge() { |
| 56 | +longest =Math.max(left.longest,right.longest); |
| 57 | +if (ca[left.end -1] ==ca[right.start]) { |
| 58 | +longest =Math.max(longest,left.rightLength +right.leftLength); |
| 59 | +leftLength = |
| 60 | + (left.leftLength ==left.end -left.start) |
| 61 | + ?left.leftLength +right.leftLength |
| 62 | + :left.leftLength; |
| 63 | +rightLength = |
| 64 | + (right.rightLength ==right.end -right.start) |
| 65 | + ?right.rightLength +left.rightLength |
| 66 | + :right.rightLength; |
| 67 | + }else { |
| 68 | +leftLength =left.leftLength; |
| 69 | +rightLength =right.rightLength; |
89 | 70 | } |
90 | | -root.max =Math.max(root.max,len); |
91 | 71 | } |
92 | 72 | } |
93 | 73 | } |