{x}
blog image

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].

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

Solution Explanation: Longest Substring of One Repeating Character

This problem requires finding the length of the longest substring containing only one repeating character after each query. A segment tree is an efficient data structure to solve this.

Approach:

We use a segment tree to efficiently handle updates and queries on the string. Each node in the segment tree represents a substring of s. The key information stored in each node is:

  • lmx: Length of the longest repeating character substring starting from the left end of the node's range.
  • rmx: Length of the longest repeating character substring ending at the right end of the node's range.
  • mx: Length of the longest repeating character substring within the node's range.

Algorithm:

  1. Build Segment Tree: Construct a segment tree from the initial string s. For leaf nodes (representing single characters), lmx, rmx, and mx are all 1. For internal nodes, these values are calculated recursively by combining the information from their children. The combination considers whether the last character of the left child's substring matches the first character of the right child's substring.

  2. Process Queries: Iterate through the queryCharacters and queryIndices. For each query:

    • Update: Modify the segment tree by changing the character at queryIndices[i] to queryCharacters[i]. This update propagates up the tree, recalculating lmx, rmx, and mx for affected nodes.
    • Query: After the update, query the root node of the segment tree to get the maximum value of mx, which represents the length of the longest repeating character substring in the updated string. Append this value to the lengths array.

  3. Return: Return the lengths array containing the length of the longest repeating substring after each query.

Time Complexity:

  • Building the segment tree takes O(n) time, where n is the length of the string.
  • Each query involves updating and querying the segment tree, both taking O(log n) time. Since we have k queries, the total time for query processing is O(k log n).
  • Therefore, the overall time complexity is O(n + k log n).

Space Complexity:

  • The segment tree requires O(n) space.
  • The lengths array takes O(k) space.
  • Therefore, the overall space complexity is O(n + k).

Code (Python):

The provided Python code implements this approach using a SegmentTree class. The build, modify, query, and pushup methods handle the segment tree operations. The Solution class processes the queries and returns the lengths array. The code includes detailed comments for better understanding.

Other Languages:

The problem solution is also provided in Java, C++, and TypeScript, demonstrating the adaptability of the segment tree approach across different programming languages. The logic remains the same across all the solutions, focusing on efficiently managing updates and queries using a segment tree to obtain the desired result in optimal time complexity.