2213. Longest Substring of One Repeating Character

Problem Overview

After each point update you need the longest run of one character in the whole string.

Intuition

After each point update you need the longest run of one character in the whole string. Rescanning is O(n) per query and too slow. A segment tree stores, for every range, the best run plus the prefix and suffix run (letter and length) so merging two halves can form a longer run that crosses the midpoint in O(1).

Algorithm

1Build a segment tree over s. A leaf is a single character with all run lengths 1.
2Merge left and right: maxLength is max of both sides, and also left.suffixLength + right.prefixLength when the boundary letters match.
3Prefix of the parent is left.prefix, extended by right.prefix only when left is entirely that letter and equals right.prefixLetter.
4Suffix is symmetric from the right child.
5For each query, update the leaf at queryIndices[i] to queryCharacters[i], rematerialize ancestors, and record root.maxLength.

Example Walkthrough

Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1, 3, 3]

1.Update index 1 to b -> "bbbacc"; longest run is bbb length 3.
2.Update index 3 to c -> "bbbccc"; longest run is ccc length 3.
3.Update index 3 to b -> "bbbbcc"; longest run is bbbb length 4.

Output: [3, 3, 4]

Common Pitfalls

•Merging must extend prefix/suffix only when the left (or right) child is fully uniform of that letter.
•Crossing the midpoint only helps when left.suffixLetter equals right.prefixLetter.
•n and q can both be 1e5 - any O(n) scan per query will TLE.
•Updates replace one character; they do not insert or delete indices.

2213.cs

// Approach: Segment tree over the string. Each node stores the longest uniform
// run inside its range, plus the prefix/suffix letter and run lengths so two
// children can merge across the midpoint when the left suffix letter matches
// the right prefix letter. Point updates recompute O(log n) ancestors.
// Complexity: O(n) build, O(q log n) time for q updates, O(n) space.
public class SegmentTreeNode
{
    public int Lo;
    public int Hi;
    public char MaxLetter;
    public char PrefixLetter;
    public char SuffixLetter;
    public int MaxLength;
    public int PrefixLength;
    public int SuffixLength;
    public SegmentTreeNode Left;
    public SegmentTreeNode Right;

    public SegmentTreeNode(
        int lo, int hi, char maxLetter, char prefixLetter, char suffixLetter,
        int maxLength, int prefixLength, int suffixLength,
        SegmentTreeNode left = null, SegmentTreeNode right = null)
    {
        Lo = lo;
        Hi = hi;
        MaxLetter = maxLetter;
        PrefixLetter = prefixLetter;
        SuffixLetter = suffixLetter;
        MaxLength = maxLength;
        PrefixLength = prefixLength;
        SuffixLength = suffixLength;
        Left = left;
        Right = right;
    }
}

public class SegmentTree
{
    private SegmentTreeNode _root;

    public SegmentTree(string s)
    {
        _root = Build(s, 0, s.Length - 1);
    }

    public void Update(int i, char val)
    {
        _root = Update(_root, i, val);
    }

    public int GetMaxLength() => _root.MaxLength;

    private SegmentTreeNode Build(string s, int lo, int hi)
    {
        if (lo == hi)
            return new SegmentTreeNode(lo, hi, s[lo], s[lo], s[lo], 1, 1, 1);

        int mid = (lo + hi) / 2;
        var left = Build(s, lo, mid);
        var right = Build(s, mid + 1, hi);
        return Merge(left, right);
    }

    private SegmentTreeNode Update(SegmentTreeNode root, int i, char c)
    {
        if (root.Lo == i && root.Hi == i)
        {
            root.MaxLetter = c;
            root.PrefixLetter = c;
            root.SuffixLetter = c;
            return root;
        }

        int mid = (root.Lo + root.Hi) / 2;
        if (i <= mid)
        {
            var updatedLeft = Update(root.Left, i, c);
            return Merge(updatedLeft, root.Right);
        }
        else
        {
            var updatedRight = Update(root.Right, i, c);
            return Merge(root.Left, updatedRight);
        }
    }

    private SegmentTreeNode Merge(SegmentTreeNode left, SegmentTreeNode right)
    {
        char maxLetter;
        int maxLength;
        if (left.MaxLength > right.MaxLength)
        {
            maxLetter = left.MaxLetter;
            maxLength = left.MaxLength;
        }
        else
        {
            maxLetter = right.MaxLetter;
            maxLength = right.MaxLength;
        }

        if (left.SuffixLetter == right.PrefixLetter &&
            left.SuffixLength + right.PrefixLength > maxLength)
        {
            maxLetter = left.SuffixLetter;
            maxLength = left.SuffixLength + right.PrefixLength;
        }

        char prefixLetter = left.PrefixLetter;
        int prefixLength = left.PrefixLength;
        if (left.Lo + prefixLength == right.Lo &&
            left.PrefixLetter == right.PrefixLetter)
            prefixLength += right.PrefixLength;

        char suffixLetter = right.SuffixLetter;
        int suffixLength = right.SuffixLength;
        if (right.Hi - suffixLength == left.Hi &&
            right.SuffixLetter == left.SuffixLetter)
            suffixLength += left.SuffixLength;

        return new SegmentTreeNode(
            left.Lo, right.Hi, maxLetter, prefixLetter, suffixLetter,
            maxLength, prefixLength, suffixLength, left, right);
    }
}

public class Solution
{
    public int[] LongestRepeating(string s, string queryCharacters, int[] queryIndices)
    {
        var ans = new int[queryIndices.Length];
        var tree = new SegmentTree(s);

        for (int i = 0; i < queryIndices.Length; i++)
        {
            tree.Update(queryIndices[i], queryCharacters[i]);
            ans[i] = tree.GetMaxLength();
        }

        return ans;
    }
}

Was this solution helpful?