Skip to main content
Talentd

Longest Substring of One Repeating Character - Solution & Explanation

HardArrayStringSegment TreeOrdered Set25 min readAsked at: Pickrr
Practice this problem

Problem Statement

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 <= 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

Approach Overview

Problem 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 1: Naive Approach with Recalculation

In this approach, after each query update, we recalculate the longest substring consisting of one repeating character for the entire string. Though simple and direct, this method can be inefficient for large strings since it checks the entire string after every update.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Sliding Window Approach

This approach employs a sliding window technique to more efficiently handle the string updates. By using two pointers, we limit recalculations to the affected region after each query, improving performance over the naive approach.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(k * m) where m is the maximum stretch of repeated characters.
Space Complexity: O(1), not including the result array.

Try this approach in the editor →

Approach 3: Segment Tree

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.

  • Each node of the segment tree represents an interval;
  • The segment tree has a unique root node, which represents the entire statistical range, such as [1, n];
  • Each leaf node of the segment tree represents an elementary interval of length 1, [x, x];
  • For each internal node [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:

  1. The number of longest consecutive characters in the prefix, lmx;
  2. The number of longest consecutive characters in the suffix, rmx;
  3. The number of longest consecutive characters in the interval, mx.
  4. The left endpoint 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Approach with Recalculation

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.

Optimized Sliding Window Approach

Time Complexity: O(k * m) where m is the maximum stretch of repeated characters.
Space Complexity: O(1), not including the result array.

Segment Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive RecalculationO(n) per queryO(1)Good for understanding the problem or when the number of updates is small
Sliding Window Style Linear ScanO(n) per queryO(1)Cleaner linear pass that tracks consecutive runs without evaluating substrings
Segment Tree OptimizationO(log n) per updateO(n)Best for large inputs with many updates where recomputation becomes too slow

Video Solution

Leetcode Weekly 285 | 2213. Longest Substring of One Repeating Character • codingMohan • 2,020 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Longest Substring of One Repeating Character easy or hard?
The problem is classified as Hard because it combines dynamic updates with substring queries. The naive solution is straightforward, but designing an efficient O(log n) update strategy using a segment tree requires strong understanding of range data structures.
Longest Substring of One Repeating Character Python/Java solution
Python and Java implementations typically either scan the string after each update or implement a segment tree to maintain segment information. The segment tree version provides O(log n) updates, while the simpler scan approach runs in O(n) per query.
How to solve Longest Substring of One Repeating Character in O(n)?
Process the string with a single linear scan that tracks consecutive runs of identical characters. Maintain a counter for the current run and update a maximum length variable whenever the run grows. After each update to the string, repeat the scan to compute the longest repeating substring in O(n) time.
What is the best approach for Longest Substring of One Repeating Character?
The most efficient solution uses a segment tree that stores the longest repeating substring length for each segment along with prefix and suffix run lengths. Each character update modifies a single leaf and recalculates parent nodes in O(log n) time. This allows the longest repeating substring to be retrieved after every query efficiently.
Is Longest Substring of One Repeating Character asked at Google/Amazon/Meta?
Problems involving dynamic string updates and longest repeating segments appear in interviews at companies like Google, Amazon, and Meta. They are commonly used to evaluate knowledge of segment trees, interval merging, and efficient update/query data structures.
What data structure is used in Longest Substring of One Repeating Character?
The optimal solution uses a segment tree. Each node stores the maximum repeating substring length inside the segment along with prefix and suffix run lengths, allowing fast recomputation when a character changes.
What is the time complexity of Longest Substring of One Repeating Character?
A simple recalculation approach scans the string after every update, giving O(n) time per query and O(n * q) overall for q updates. A segment tree optimization reduces update time to O(log n) while maintaining the longest repeating substring in each node.

Ready to solve this problem?

Practice Longest Substring of One Repeating Character with our built-in code editor and test cases.

Practice on FleetCode
Previous

Consecutive Characters

Next

Create Sorted Array through Instructions