1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128 | struct SegmentTreeNode {
int lo;
int hi;
char maxLetter;
char prefixLetter;
char suffixLetter;
int maxLength;
int prefixLength;
int suffixLength;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int lo, int hi, char maxLetter, char prefixLetter,
char suffixLetter, int maxLength, int prefixLength,
int suffixLength, SegmentTreeNode* left = nullptr,
SegmentTreeNode* right = nullptr)
: lo(lo),
hi(hi),
maxLetter(maxLetter),
prefixLetter(prefixLetter),
suffixLetter(suffixLetter),
maxLength(maxLength),
prefixLength(prefixLength),
suffixLength(suffixLength),
left(left),
right(right) {}
~SegmentTreeNode() {
delete left;
delete right;
left = nullptr;
right = nullptr;
}
};
class SegmentTree {
public:
explicit SegmentTree(const string& s) : root(build(s, 0, s.length() - 1)) {}
~SegmentTree() {
delete root;
}
void update(int i, char val) {
root = update(root, i, val);
}
int getMaxLength() {
return root->maxLength;
}
private:
SegmentTreeNode* root;
SegmentTreeNode* build(const string& s, int lo, int hi) const {
if (lo == hi)
return new SegmentTreeNode(lo, hi, s[lo], s[lo], s[lo], 1, 1, 1);
const int mid = (lo + hi) / 2;
SegmentTreeNode* left = build(s, lo, mid);
SegmentTreeNode* right = build(s, mid + 1, hi);
return merge(left, right);
}
SegmentTreeNode* update(SegmentTreeNode* root, int i, char c) {
if (root->lo == i && root->hi == i) {
root->maxLetter = c;
root->prefixLetter = c;
root->suffixLetter = c;
return root;
}
const int mid = (root->lo + root->hi) / 2;
if (i <= mid) {
SegmentTreeNode* updatedLeft = update(root->left, i, c);
return root = merge(updatedLeft, root->right);
} else {
SegmentTreeNode* updatedRight = update(root->right, i, c);
return root = merge(root->left, updatedRight);
}
}
SegmentTreeNode* merge(SegmentTreeNode* left, SegmentTreeNode* right) const {
// Get `maxLetter` and `maxLength`.
char maxLetter = ' ';
int maxLength = 0;
if (left->maxLength > right->maxLength) {
maxLetter = left->maxLetter;
maxLength = left->maxLength;
} else {
maxLetter = right->maxLetter;
maxLength = right->maxLength;
}
if (left->suffixLetter == right->prefixLetter &&
left->suffixLength + right->prefixLength > maxLength) {
maxLetter = left->suffixLetter;
maxLength = left->suffixLength + right->prefixLength;
}
// Get `prefixLetter` and `prefixLength`.
char prefixLetter = left->prefixLetter;
int prefixLength = left->prefixLength;
if (left->lo + prefixLength == right->lo &&
left->prefixLetter == right->prefixLetter)
prefixLength += right->prefixLength;
// Get `suffixLetter` and `suffixLength`.
char suffixLetter = right->suffixLetter;
int suffixLength = right->suffixLength;
if (right->hi - suffixLength == left->hi &&
right->suffixLetter == left->suffixLetter)
suffixLength += left->suffixLength;
return new SegmentTreeNode(left->lo, right->hi, maxLetter, prefixLetter,
suffixLetter, maxLength, prefixLength,
suffixLength, left, right);
}
};
class Solution {
public:
vector<int> longestRepeating(string s, string queryLetteracters,
vector<int>& queryIndices) {
vector<int> ans;
SegmentTree tree(s);
for (int i = 0; i < queryIndices.size(); ++i) {
tree.update(queryIndices[i], queryLetteracters[i]);
ans.push_back(tree.getMaxLength());
}
return ans;
}
};
|
