2213. Longest Substring of One Repeating Character LeetCode Solution
In this guide, you will get 2213. Longest Substring of One Repeating Character LeetCode Solution with the best time and space complexity. The solution to Longest Substring of One Repeating Character problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Longest Substring of One Repeating Character
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].
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
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
2213. Longest Substring of One Repeating Character LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
2213. Longest Substring of One Repeating Character LeetCode Solution in Java
N/A // code provided by PROGIEZ
2213. Longest Substring of One Repeating Character LeetCode Solution in Python
