LeetCode 2213 - Longest Substring of One Repeating Character

Difficulty: 🔴 Hard
Topics: Array, String, Segment Tree, Ordered Set

Solution

Problem Understanding

The problem gives us an initial string s and a sequence of update operations. Each update changes exactly one character in the string. After every update, we must determine the length of the longest contiguous substring that contains only one repeating character.

A substring is contiguous, so characters must appear next to each other. For example, in "aaabbcccc", the longest repeating substring is "cccc" with length 4.

Each query consists of two parts:

queryIndices[i], the position in the string to modify
queryCharacters[i], the new character to place at that position

After applying the update, we immediately compute the answer for the modified string and store it in the result array.

The constraints are very important:

s.length can be up to 10^5
Number of queries can also be up to 10^5

A naive recomputation after every update would be far too slow. Even an O(n) scan per query would lead to O(n * k) complexity, which could become 10^10 operations in the worst case.

This immediately suggests that we need a data structure capable of:

Updating a single position efficiently
Maintaining the longest repeating substring efficiently

The core challenge is that changing one character can affect neighboring segments. For example:

aaaabaaa

If the middle 'b' becomes 'a', two separate runs merge into one large run:

aaaaaaaa

Likewise, a change can split a run into smaller pieces.

Important edge cases include:

Strings of length 1
Updates that do not actually change the character
Updates that merge two neighboring runs
Updates that split a previously large run
Strings where all characters are identical
Alternating strings like "abababab"

The problem guarantees valid indices and lowercase English letters, so we do not need to handle invalid input.

Approaches

Brute Force Approach

The simplest approach is:

Apply each update directly to the string
Scan the entire string from left to right
Track the longest contiguous block of identical characters

For every query, we compare adjacent characters and count streak lengths.

This approach is correct because it explicitly recomputes the answer from the updated string every time.

However, its performance is unacceptable.

If:

n = 10^5
k = 10^5

Then scanning the entire string after each query costs:

O(n * k) = O(10^10)

which is far too slow.

Optimal Approach, Segment Tree

The key observation is that a single character update only affects a small local region, but the longest repeating substring is a global property.

This is a classic scenario for a segment tree.

We build a segment tree where every node stores enough information about its segment to combine two child segments efficiently.

For every segment, we store:

left_char, the first character in the segment
right_char, the last character in the segment
prefix, length of the longest repeating prefix
suffix, length of the longest repeating suffix
best, longest repeating substring anywhere in the segment
length, total segment length

When combining two child segments:

The best answer may lie entirely in the left child
Entirely in the right child
Or cross the boundary if the adjacent characters match

This allows updates and queries in O(log n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(1)	Recompute longest run after every update
Optimal	O((n + k) log n)	O(n)	Segment tree maintains longest repeating substring dynamically

Algorithm Walkthrough

Build a segment tree over the string.

Every node represents a contiguous interval of the string. Instead of storing only one value, each node stores enough information to reconstruct the answer when two segments are merged. 2. Store metadata for each segment.

For each node, we maintain:

The leftmost character
The rightmost character
Longest repeating prefix
Longest repeating suffix
Longest repeating substring inside the segment
Segment length

This information is sufficient to merge two neighboring segments correctly. 3. Handle leaf nodes.

A leaf represents a single character.

For a single character:

Prefix length = 1
Suffix length = 1
Best length = 1

Merge two child nodes.

Suppose we merge left segment A and right segment B.

The combined segment length is:

A.length + B.length

The combined best answer is initially:

max(A.best, B.best)

If:

A.right_char == B.left_char

then a repeating substring can cross the boundary.

In that case:

cross = A.suffix + B.prefix

and we update:

best = max(best, cross)

Compute prefix length.

If the entire left segment consists of the same character and it matches the right segment's first character, then the repeating prefix extends into the right child. 6. Compute suffix length.

Similarly, if the entire right segment is uniform and matches the left segment's last character, then the repeating suffix extends into the left child. 7. Process updates.

For every query:

Update the leaf corresponding to the changed index
Recompute all ancestors on the path back to the root

Since the height of the segment tree is O(log n), updates are efficient. 8. Read the answer.

The root node always stores the answer for the entire string.

After each update, append:

tree[1].best

to the result list.

Why it works

The segment tree maintains complete information about every interval. Any longest repeating substring inside a parent interval must be one of three possibilities:

Entirely inside the left child
Entirely inside the right child
Crossing the boundary between the children

The stored prefix and suffix lengths are exactly what is needed to evaluate the third case. Because every merge computes correct values from correct child nodes, the entire tree remains correct after every update.

Python Solution

from typing import List

class Node:
    def __init__(self):
        self.left_char = ""
        self.right_char = ""
        self.prefix = 0
        self.suffix = 0
        self.best = 0
        self.length = 0

class Solution:
    def longestRepeating(
        self,
        s: str,
        queryCharacters: str,
        queryIndices: List[int]
    ) -> List[int]:

        chars = list(s)
        n = len(chars)

        tree = [Node() for _ in range(4 * n)]

        def merge(left: Node, right: Node) -> Node:
            node = Node()

            node.length = left.length + right.length
            node.left_char = left.left_char
            node.right_char = right.right_char

            node.prefix = left.prefix
            if (
                left.prefix == left.length and
                left.right_char == right.left_char
            ):
                node.prefix = left.length + right.prefix

            node.suffix = right.suffix
            if (
                right.suffix == right.length and
                left.right_char == right.left_char
            ):
                node.suffix = right.length + left.suffix

            node.best = max(left.best, right.best)

            if left.right_char == right.left_char:
                node.best = max(
                    node.best,
                    left.suffix + right.prefix
                )

            return node

        def build(index: int, left: int, right: int) -> None:
            if left == right:
                node = tree[index]

                node.left_char = chars[left]
                node.right_char = chars[left]
                node.prefix = 1
                node.suffix = 1
                node.best = 1
                node.length = 1
                return

            mid = (left + right) // 2

            build(index * 2, left, mid)
            build(index * 2 + 1, mid + 1, right)

            tree[index] = merge(
                tree[index * 2],
                tree[index * 2 + 1]
            )

        def update(
            index: int,
            left: int,
            right: int,
            position: int,
            character: str
        ) -> None:

            if left == right:
                chars[position] = character

                node = tree[index]
                node.left_char = character
                node.right_char = character
                node.prefix = 1
                node.suffix = 1
                node.best = 1
                node.length = 1
                return

            mid = (left + right) // 2

            if position <= mid:
                update(
                    index * 2,
                    left,
                    mid,
                    position,
                    character
                )
            else:
                update(
                    index * 2 + 1,
                    mid + 1,
                    right,
                    position,
                    character
                )

            tree[index] = merge(
                tree[index * 2],
                tree[index * 2 + 1]
            )

        build(1, 0, n - 1)

        answer = []

        for character, position in zip(queryCharacters, queryIndices):
            update(1, 0, n - 1, position, character)
            answer.append(tree[1].best)

        return answer

The implementation begins by converting the string into a mutable list because Python strings are immutable. A segment tree array is then allocated with size 4 * n, which safely accommodates all tree nodes.

The Node class stores all metadata required for merging segments. This includes prefix and suffix lengths, the best answer inside the interval, and the boundary characters.

The merge function is the heart of the algorithm. It combines two child segments into one parent segment. The logic carefully handles the possibility that a repeating substring spans across the midpoint.

The build function recursively constructs the initial segment tree. Leaf nodes correspond to single characters, while internal nodes are produced through merging.

The update function recursively descends to the modified position, updates the leaf node, and then recomputes all affected ancestors.

After every query, the root node stores the answer for the entire string, so tree[1].best is appended directly to the result.

Go Solution

package main

type Node struct {
	leftChar  byte
	rightChar byte
	prefix    int
	suffix    int
	best      int
	length    int
}

func longestRepeating(s string, queryCharacters string, queryIndices []int) []int {
	chars := []byte(s)
	n := len(chars)

	tree := make([]Node, 4*n)

	var merge func(Node, Node) Node

	merge = func(left Node, right Node) Node {
		node := Node{}

		node.length = left.length + right.length
		node.leftChar = left.leftChar
		node.rightChar = right.rightChar

		node.prefix = left.prefix
		if left.prefix == left.length &&
			left.rightChar == right.leftChar {
			node.prefix = left.length + right.prefix
		}

		node.suffix = right.suffix
		if right.suffix == right.length &&
			left.rightChar == right.leftChar {
			node.suffix = right.length + left.suffix
		}

		if left.best > right.best {
			node.best = left.best
		} else {
			node.best = right.best
		}

		if left.rightChar == right.leftChar {
			cross := left.suffix + right.prefix
			if cross > node.best {
				node.best = cross
			}
		}

		return node
	}

	var build func(int, int, int)

	build = func(index int, left int, right int) {
		if left == right {
			tree[index] = Node{
				leftChar:  chars[left],
				rightChar: chars[left],
				prefix:    1,
				suffix:    1,
				best:      1,
				length:    1,
			}
			return
		}

		mid := (left + right) / 2

		build(index*2, left, mid)
		build(index*2+1, mid+1, right)

		tree[index] = merge(
			tree[index*2],
			tree[index*2+1],
		)
	}

	var update func(int, int, int, int, byte)

	update = func(
		index int,
		left int,
		right int,
		position int,
		character byte,
	) {

		if left == right {
			chars[position] = character

			tree[index] = Node{
				leftChar:  character,
				rightChar: character,
				prefix:    1,
				suffix:    1,
				best:      1,
				length:    1,
			}
			return
		}

		mid := (left + right) / 2

		if position <= mid {
			update(index*2, left, mid, position, character)
		} else {
			update(index*2+1, mid+1, right, position, character)
		}

		tree[index] = merge(
			tree[index*2],
			tree[index*2+1],
		)
	}

	build(1, 0, n-1)

	answer := make([]int, 0, len(queryIndices))

	for i := 0; i < len(queryIndices); i++ {
		update(
			1,
			0,
			n-1,
			queryIndices[i],
			queryCharacters[i],
		)

		answer = append(answer, tree[1].best)
	}

	return answer
}

The Go implementation closely mirrors the Python version, but several language-specific differences are worth noting.

Go strings are immutable, so the string is converted into a []byte slice for efficient updates.

The segment tree is stored as a slice of Node structs. Structs are value types in Go, so merges return complete Node values.

Go does not support nested named functions directly, so recursive closures are declared using var functionName func(...).

All integers comfortably fit inside Go's default int type because the maximum value involved is at most 10^5.

Worked Examples

Example 1

Input:

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

Initial runs:

Substring	Length
b	1
a	1
b	1
a	1
cc	2

Initial best = 2.

Query 1

Update index 1 to 'b'.

babacc -> bbbacc

Runs become:

Substring	Length
bbb	3
a	1
cc	2

Best = 3.

Result array:

[3]

Query 2

Update index 3 to 'c'.

bbbacc -> bbbccc

Runs become:

Substring	Length
bbb	3
ccc	3

Best = 3.

Result array:

[3, 3]

Query 3

Update index 3 to 'b'.

bbbccc -> bbbbcc

Runs become:

Substring	Length
bbbb	4
cc	2

Best = 4.

Final answer:

[3, 3, 4]

Example 2

Input:

s = "abyzz"
queryCharacters = "aa"
queryIndices = [2,1]

Initial runs:

Substring	Length
a	1
b	1
y	1
zz	2

Initial best = 2.

Query 1

Update index 2 to 'a'.

abyzz -> abazz

Runs:

Substring	Length
a	1
b	1
a	1
zz	2

Best = 2.

Query 2

Update index 1 to 'a'.

abazz -> aaazz

Runs:

Substring	Length
aaa	3
zz	2

Best = 3.

Final answer:

[2, 3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + k) log n)	Building costs O(n), each update costs O(log n)
Space	O(n)	Segment tree storage

Building the segment tree requires visiting every node once, which costs O(n).

Each query performs a single point update. Since the segment tree height is O(log n), only logarithmically many nodes must be recomputed.

The tree itself contains at most about 4n nodes, so the space complexity is linear.

Test Cases

from typing import List

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        class Node:
            def __init__(self):
                self.left_char = ""
                self.right_char = ""
                self.prefix = 0
                self.suffix = 0
                self.best = 0
                self.length = 0

        chars = list(s)
        n = len(chars)

        tree = [Node() for _ in range(4 * n)]

        def merge(left: Node, right: Node) -> Node:
            node = Node()

            node.length = left.length + right.length
            node.left_char = left.left_char
            node.right_char = right.right_char

            node.prefix = left.prefix
            if left.prefix == left.length and left.right_char == right.left_char:
                node.prefix = left.length + right.prefix

            node.suffix = right.suffix
            if right.suffix == right.length and left.right_char == right.left_char:
                node.suffix = right.length + left.suffix

            node.best = max(left.best, right.best)

            if left.right_char == right.left_char:
                node.best = max(node.best, left.suffix + right.prefix)

            return node

        def build(index: int, left: int, right: int):
            if left == right:
                node = tree[index]
                node.left_char = chars[left]
                node.right_char = chars[left]
                node.prefix = 1
                node.suffix = 1
                node.best = 1
                node.length = 1
                return

            mid = (left + right) // 2

            build(index * 2, left, mid)
            build(index * 2 + 1, mid + 1, right)

            tree[index] = merge(
                tree[index * 2],
                tree[index * 2 + 1]
            )

        def update(index: int, left: int, right: int, pos: int, ch: str):
            if left == right:
                chars[pos] = ch

                node = tree[index]
                node.left_char = ch
                node.right_char = ch
                node.prefix = 1
                node.suffix = 1
                node.best = 1
                node.length = 1
                return

            mid = (left + right) // 2

            if pos <= mid:
                update(index * 2, left, mid, pos, ch)
            else:
                update(index * 2 + 1, mid + 1, right, pos, ch)

            tree[index] = merge(
                tree[index * 2],
                tree[index * 2 + 1]
            )

        build(1, 0, n - 1)

        result = []

        for ch, idx in zip(queryCharacters, queryIndices):
            update(1, 0, n - 1, idx, ch)
            result.append(tree[1].best)

        return result

solver = Solution()

assert solver.longestRepeating(
    "babacc",
    "bcb",
    [1, 3, 3]
) == [3, 3, 4]  # provided example 1

assert solver.longestRepeating(
    "abyzz",
    "aa",
    [2, 1]
) == [2, 3]  # provided example 2

assert solver.longestRepeating(
    "a",
    "b",
    [0]
) == [1]  # single character string

assert solver.longestRepeating(
    "aaaa",
    "bbbb",
    [0, 1, 2, 3]
) == [3, 2, 3, 4]  # repeated splitting and merging

assert solver.longestRepeating(
    "abcd",
    "dddd",
    [0, 1, 2, 3]
) == [2, 3, 4, 4]  # gradual merge into one run

assert solver.longestRepeating(
    "zzzz",
    "zz",
    [1, 2]
) == [4, 4]  # updates that do not change anything

assert solver.longestRepeating(
    "ababab",
    "aaaaaa",
    [1, 3, 5, 0, 2, 4]
) == [3, 5, 6, 6, 6, 6]  # alternating pattern becoming uniform

assert solver.longestRepeating(
    "abcde",
    "eeeee",
    [0, 1, 2, 3, 4]
) == [2, 2, 3, 4, 5]  # repeated right-side extension

Test	Why
`"babacc"` example	Validates standard updates
`"abyzz"` example	Validates separated runs
Single character string	Smallest valid input
`"aaaa"` to `"bbbb"`	Tests splitting and rebuilding runs
`"abcd"` gradual merge	Tests repeated merging
No-op updates	Ensures unchanged updates work correctly
Alternating string	Stress test for repeated merges
Right-side extension	Tests prefix/suffix propagation

Edge Cases

One important edge case is when the string length is 1. In this scenario, every query still produces an answer of 1 because a single character always forms a repeating substring of length 1. The implementation handles this naturally because every leaf node has best = 1.

Another critical case occurs when an update does not actually change the character. For example:

"aaaa"

updating index 2 to 'a'.

A buggy implementation might unnecessarily alter internal state or accidentally break merge logic. The segment tree implementation safely rebuilds the affected path, and because all merge rules remain valid, the answer stays unchanged.

A third tricky case happens when two large runs merge across an updated position. Consider:

aaabaaa

If the middle 'b' becomes 'a', the answer suddenly jumps from 3 to 7. The merge logic specifically handles this by checking whether the rightmost character of the left child equals the leftmost character of the right child. If so, suffix and prefix lengths are combined correctly.

Another subtle case occurs when a large run is split apart. For example:

aaaaa

Changing the middle character to 'b' creates:

aabaa

The best answer drops from 5 to 2. Because updates rebuild all ancestor nodes from scratch using current child values, stale information never persists in the tree.