Longest Substring of One Repeating Character

Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input:
s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
Output:
 [3,3,4]
Explanation: 
- 1st query updates s = "b**b**bacc". The longest substring consisting of one repeating character is "bbb" with length 3.
- 2nd query updates s = "bbb**c**cc". 
  The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3.
- 3rd query updates s = "bbb**b**cc". The longest substring consisting of one repeating character is "bbbb" with length 4.
Thus, we return [3,3,4].

Example 2:

1
2
3
4
5
6
7
8


Input:
s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
Output:
 [2,3]
Explanation:
- 1st query updates s = "ab**a**zz". The longest substring consisting of one repeating character is "zz" with length 2.
- 2nd query updates s = "a**a**azz". The longest substring consisting of one repeating character is "aaa" with length 3.
Thus, we return [2,3].

Solution

This problem requires tracking and updating the longest consecutive substring of identical characters in s after every query. Each query modifies a character, which affects the longest substring.

Method 1 - Using sliding window

Approach

Initial Setup:
- Compute the initial longest substring of identical characters from the input string s.
- Store the start and end positions of contiguous substrings in an array or list.
Perform Updates:
- For each query (queryCharacters[i], queryIndices[i]), update the string at the specified index.
- Update the tracking of contiguous substrings based on changes.
Update Calculation:
- Updates might split, merge or alter the lengths of contiguous substrings.
- Recalculate the longest substring length after each query.
Store Results:
- Append the longest substring length for each update to the output list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {
    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
        int n = queryIndices.length;
        int[] ans = new int[n];
        
        // Helper function to calculate the longest substring of repeating characters
        int calculateMaxLength(String s) {
            int maxLen = 0, currLen = 1;
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == s.charAt(i - 1)) {
                    currLen++;
                } else {
                    maxLen = Math.max(maxLen, currLen);
                    currLen = 1;
                }
            }
            maxLen = Math.max(maxLen, currLen);
            return maxLen;
        }
        
        int maxLen = calculateMaxLength(s);
        
        for (int i = 0; i < n; i++) {
            int idx = queryIndices[i];
            char ch = queryCharacters.charAt(i);
            
            // Update character in `s`
            StringBuilder sb = new StringBuilder(s);
            sb.setCharAt(idx, ch);
            s = sb.toString();
            
            // Recalculate max length
            maxLen = calculateMaxLength(s);
            ans[i] = maxLen;
        }
        
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        def calculate_max_length(s: str) -> int:
            max_len = 0
            curr_len = 1
            for i in range(1, len(s)):
                if s[i] == s[i - 1]:
                    curr_len += 1
                else:
                    max_len = max(max_len, curr_len)
                    curr_len = 1
            max_len = max(max_len, curr_len)
            return max_len
        
        ans: List[int] = []
        max_len = calculate_max_length(s)
        
        for i in range(len(queryIndices)):
            idx = queryIndices[i]
            ch = queryCharacters[i]
            
            # Update character in `s`
            temp = list(s)
            temp[idx] = ch
            s = "".join(temp)
            
            # Recalculate max length
            max_len = calculate_max_length(s)
            ans.append(max_len)
        
        return ans

Complexity

⏰ Time complexity: O(n + k) where n is the length of s and k is the number of queries. Calculating the initial substring lengths involves O(n), and processing each query takes O(1) as adjustments are local.
🧺 Space complexity: O(n) due to storage for tracking substrings.

Problem#

Examples#

Solution#

Method 1 - Using sliding window#

Approach#

Code#

Complexity#