Watch 5 video solutions for Longest Substring of One Repeating Character, a hard level problem involving Array, String, Segment Tree. This walkthrough by codingMohan has 1,936 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |