Longest Substring of One Repeating Character

Longest Substring of One Repeating Character

What is this problem about?

In this problem, you are given a string s and a series of query updates. Each query provides an index and a character, instructing you to replace the character in s at that specific index. After each query, you must return the length of the longest contiguous substring that consists of a single repeating character (e.g., "bb" in "abbc").

Why is this asked in interviews?

This is a Hard-level problem that directly tests your knowledge of advanced data structures. Interviewers ask this to see if you can identify when standard array traversals fail. If you rescan the string after every single query, your time complexity will be $O(Q \times N)$, which results in a Time Limit Exceeded error. You must demonstrate the ability to update and query states in $O(\log N)$ time.

Algorithmic pattern used

The definitive algorithmic pattern for this problem is the Segment Tree. A Segment Tree can efficiently manage range queries and point updates. Each node in the Segment Tree will represent a segment of the string and store: the longest repeating prefix, the longest repeating suffix, the character of the prefix, the character of the suffix, and the overall maximum repeating substring length within that segment. When an update occurs, you modify a leaf node and recalculate upwards to the root in $O(\log N)$ time.

Example explanation

String: "bab". Query: Replace index 0 with 'b'. String becomes "bbb".

• Without a Segment Tree, you would scan "bbb" to find the max length is 3. Query: Replace index 1 with 'a'. String becomes "bab".
• With a Segment Tree: The tree knows the left leaf is 'b' (len 1) and the right leaf is 'b' (len 1), but the middle is now 'a'. When the tree merges the segments, it sees the prefix of the right segment ('b') does not match the suffix of the left segment ('a'). Therefore, they don't combine. The overall max length returned is 1.

Common mistakes candidates make

The most frequent mistake is trying to solve this using a Hash Map or Ordered Set to keep track of indices where characters change. While an Ordered Set can work by tracking the boundaries of character blocks, it is notoriously tricky to implement in interviews without off-by-one errors. Another mistake is writing a Segment Tree but forgetting to merge the suffix of the left child with the prefix of the right child when they share the same character.

Interview preparation tip

To excel at the Longest Substring of One Repeating Character coding problem, you must practice writing Segment Trees that handle "merge" logic. Learn how to write a custom Node class for your tree. The key to merging is checking: if leftChild.suffixChar == rightChild.prefixChar, then you can potentially form a new max length spanning across the two children: leftChild.suffixLen + rightChild.prefixLen.