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 <= 105s consists of lowercase English letters.k == queryCharacters.length == queryIndices.length1 <= k <= 105queryCharacters consists of lowercase English letters.0 <= queryIndices[i] < s.lengthProblem Overview: You start with a string s. Each query updates a single index with a new character. After every update, return the length of the longest substring consisting of only one repeating character. The challenge is efficiently recomputing this value after each modification.
Approach 1: Naive Approach with Recalculation (O(n) per query, O(1) space)
After each character update, recompute the longest repeating substring by scanning the entire string. Iterate through s while tracking the length of the current run of identical characters and the global maximum. Whenever the character changes, reset the run counter and continue. This approach uses only a few variables and works for any string size, but every query forces a full pass over the array. If there are q updates and the string length is n, the total complexity becomes O(n * q). It’s simple and reliable but too slow when both n and q are large.
Approach 2: Optimized Sliding Window Style Scan (O(n) per query, O(1) space)
A more structured scan treats consecutive identical characters as windows. Maintain two pointers representing the current run of repeating characters. As you iterate through the string, extend the window while characters match and shrink/reset when they differ. Each update modifies only one index, so the string is scanned once to rebuild the longest run information. The key idea is tracking run lengths directly instead of evaluating all possible substrings. This keeps the logic linear and avoids redundant comparisons. Although each query still requires an O(n) pass, the implementation is clean and predictable, making it suitable when constraints are moderate.
For very large constraints, production-grade solutions typically rely on a segment tree that stores prefix, suffix, and maximum repeating lengths for each segment of the array. Updates then take O(log n). The simplified approaches here focus on clarity and correctness rather than advanced tree structures.
Recommended for interviews: Start with the naive recalculation approach to demonstrate understanding of the problem and how repeating segments are detected. Then discuss how repeated scans become expensive with many queries. Interviewers usually expect you to mention a segment tree or interval-based structure for O(log n) updates. Showing the progression from brute force scanning to a structured data structure demonstrates both problem-solving clarity and optimization awareness.
This C solution recalculates after each query by iterating through the updated string to find the longest repeating substring of one character. We update the string on each iteration and use a helper function to find the maximum consecutive characters by maintaining a count of consecutive matching characters and updating the maximum count.
Time Complexity: O(k * n), where n is the length of the string.
Space Complexity: O(1), as we use a constant amount of extra space.
This optimized C solution employs a modified sliding window approach. After each query, it recalculates the max length only in the region affected by the change, reducing recalculation overhead.
Time Complexity: O(k * m) where m is the maximum stretch of repeated characters.
Space Complexity: O(1), not including the result array.
The segment tree divides the entire interval into multiple non-continuous sub-intervals, and the number of sub-intervals does not exceed log(width). To update the value of an element, you only need to update log(width) intervals, and these intervals are all contained in a large interval that contains the element. When modifying the interval, you need to use lazy tags to ensure efficiency.
[1, n];1, [x, x];[l, r], its left child is [l, mid], and the right child is [mid + 1, r], where mid = \frac{l + r}{2};For this problem, the information maintained by the segment tree node includes:
lmx;rmx;mx.l and the right endpoint r of the interval.The time complexity is O(n times log n), and the space complexity is O(n times log n). Where n is the length of the string s.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Naive Approach with Recalculation | Time Complexity: O(k * n), where n is the length of the string. |
| Optimized Sliding Window Approach | Time Complexity: O(k * m) where m is the maximum stretch of repeated characters. |
| Segment Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Recalculation | O(n) per query | O(1) | Good for understanding the problem or when the number of updates is small |
| Sliding Window Style Linear Scan | O(n) per query | O(1) | Cleaner linear pass that tracks consecutive runs without evaluating substrings |
| Segment Tree Optimization | O(log n) per update | O(n) | Best for large inputs with many updates where recomputation becomes too slow |
Leetcode Weekly 285 | 2213. Longest Substring of One Repeating Character • codingMohan • 1,936 views views
Watch 4 more video solutions →Practice Longest Substring of One Repeating Character with our built-in code editor and test cases.
Practice on FleetCode