Longest Substring of One Repeating Character

Problem Description

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.

Key Insights

• Each query modifies a single character in the string s, potentially changing the longest substring of repeating characters.
• The problem can be approached by finding the longest contiguous block of the same character in the string.
• Efficiently updating the string and recalculating the longest substring after each query is crucial due to constraints.

Space and Time Complexity

Time Complexity: O(k * n), where n is the length of the string s and k is the number of queries. In the worst case, recalculating the longest substring may require scanning the entire string for each query.

Space Complexity: O(1), since we are using a constant amount of additional space, not counting the output array.

Solution

To solve this problem, we can follow these steps:

1. For each query, update the character in the string s at the specified index.
2. After each update, iterate through the string to find the longest substring consisting of the same character:
   • Use a counter to track the length of the current substring.
   • Update a maximum length variable whenever we encounter a different character.
3. Store the maximum length found after each query in an output array.

By efficiently iterating through the string after each update, we can keep track of the longest substring of repeating characters.

Code Solutions