LeetCode Solutions Blog

Longest Substring of One Repeating Character

Number: 2319

Difficulty: Hard

Paid? No

Companies: Pickrr

Problem Description

Given a string s and k queries where each query updates the character at a specified index in s, return an array of k values such that the ith value is the length of the longest contiguous substring consisting of a single repeating character after performing the ith query.

Key Insights

Only one character is updated per query, so only adjacent segments may need to be split or merged.
It is efficient to represent s as a collection of segments, where each segment is a consecutive block of identical characters.
An update may split an existing segment and then potentially merge with neighboring segments if they have the same character as the newly updated character.
Data structures like balanced binary search trees or ordered sets can be leveraged to quickly identify and update segments.
Alternatively, a direct simulation using a sorted list (or array) of segments is sufficient with proper binary search for locating the segment affected by each update.

Space and Time Complexity

Time Complexity: O((N + Q) log N) in the worst case, where N is the length of s and Q is the number of queries. Space Complexity: O(N) for storing the segments.

Solution

The solution creates segments representing blocks of identical characters. For every query:

Find the segment that includes the update index.
Remove that segment and split it into up to two segments if the update occurs in the middle.
Insert a new segment at the updated position.
Merge the new segment with adjacent segments if they contain the same character.
Recalculate (or update) the longest segment length. This approach ensures that only segments possibly affected by the update are processed and merged, maintaining overall efficiency.

Code Solutions

# Python solution using a list of segments and binary search for the update position.

class Segment:
    def __init__(self, start, end, char):
        self.start = start
        self.end = end
        self.char = char

    def length(self):
        return self.end - self.start + 1

def longest_substring_after_queries(s, queryCharacters, queryIndices):
    n = len(s)
    s = list(s)  # Convert string to list for mutable updates
    segments = []
    i = 0
    # Build initial segments of consecutive identical characters.
    while i < n:
        j = i
        while j + 1 < n and s[j + 1] == s[i]:
            j += 1
        segments.append(Segment(i, j, s[i]))
        i = j + 1

    # Binary search to locate the segment containing position pos.
    def find_segment(pos):
        lo, hi = 0, len(segments) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            seg = segments[mid]
            if seg.start <= pos <= seg.end:
                return mid
            elif pos < seg.start:
                hi = mid - 1
            else:
                lo = mid + 1
        return None

    longest = max(seg.length() for seg in segments)
    result = []

    # Process each query.
    for char, pos in zip(queryCharacters, queryIndices):
        if s[pos] == char:
            result.append(longest)
            continue

        seg_index = find_segment(pos)
        seg = segments.pop(seg_index)
        
        # Create left and right segments for unchanged parts.
        left_seg = Segment(seg.start, pos - 1, seg.char) if seg.start < pos else None
        right_seg = Segment(pos + 1, seg.end, seg.char) if pos < seg.end else None
        
        s[pos] = char
        new_seg = Segment(pos, pos, char)
        
        insertion_index = seg_index
        if left_seg:
            segments.insert(insertion_index, left_seg)
            insertion_index += 1
        segments.insert(insertion_index, new_seg)
        insertion_index += 1
        if right_seg:
            segments.insert(insertion_index, right_seg)

        # Merge with left segment if same character.
        if insertion_index - 2 >= 0 and segments[insertion_index - 2].char == new_seg.char:
            segments[insertion_index - 2].end = new_seg.end
            segments.pop(insertion_index - 1)
            new_seg = segments[insertion_index - 2]
            insertion_index -= 1

        # Merge with right segment if same character.
        if insertion_index < len(segments) and segments[insertion_index].char == new_seg.char:
            new_seg.end = segments[insertion_index].end
            segments.pop(insertion_index)

        longest = max(seg.length() for seg in segments)
        result.append(longest)
    
    return result

# Example usage:
print(longest_substring_after_queries("babacc", "bcb", [1,3,3]))  # Expected output: [3,3,4]