LeetCode 3777 - Minimum Deletions to Make Alternating Substring

We are given a mutable binary string consisting only of 'A' and 'B'. There are two kinds of queries: - [1, j] flips the character at position j. If it was 'A', it becomes 'B', and vice versa. This permanently changes the string and affects all future queries.

leetcodehardstringsegment-tree

LeetCode Problem 3777

Difficulty: 🔴 Hard
Topics: String, Segment Tree

Solution

Problem Understanding

We are given a mutable binary string consisting only of 'A' and 'B'.

There are two kinds of queries:

  • [1, j] flips the character at position j. If it was 'A', it becomes 'B', and vice versa. This permanently changes the string and affects all future queries.
  • [2, l, r] asks for the minimum number of deletions required to make the substring s[l..r] alternating.

A string is alternating if no two adjacent characters are equal. Examples:

  • "ABAB" is alternating.
  • "BABA" is alternating.
  • "AAB" is not alternating.
  • "BBB" is not alternating.

The important detail is that we are only allowed to delete characters. We cannot reorder characters.

For a substring of length m, if the longest alternating subsequence inside that substring has length L, then we must delete exactly m - L characters. Therefore, every query of type 2 reduces to:

Find the length of the longest alternating subsequence in s[l..r].

The constraints are large:

  • n ≤ 100000
  • q ≤ 100000

A solution that scans the substring for every query would be far too slow. We need a data structure that supports both point updates and range queries efficiently.

Some important edge cases are:

  • A substring of length 1 is already alternating.
  • A substring containing only one character repeated many times has longest alternating subsequence length 1.
  • Updates can completely change the answer for future queries.
  • Queries may cover the entire string.

Approaches

Brute Force

For every query [2, l, r], we could extract the substring and compute the longest alternating subsequence directly.

Since the alphabet contains only two characters, a dynamic programming solution can find the longest alternating subsequence in linear time with respect to the substring length.

However, in the worst case:

  • Each query may examine O(n) characters.
  • There may be O(n) queries.

This leads to O(nq) time, which can reach 10^10 operations and is completely infeasible.

Key Insight

The minimum deletions equal:

$$\text{length of substring} - \text{longest alternating subsequence length}$$

So the real challenge is maintaining the longest alternating subsequence under point updates.

The longest alternating subsequence can be modeled as a small finite-state dynamic program.

We maintain three DP states:

  • Start , no character chosen yet
  • A , last chosen character is 'A'
  • B , last chosen character is 'B'

For a single character, we can describe all valid DP transitions using a small 3 × 3 max-plus matrix.

A substring then becomes the product of the matrices corresponding to its characters.

Because matrix multiplication is associative, a segment tree can store the matrix for every segment:

  • Point update: replace one leaf matrix.
  • Range query: multiply matrices over the interval.

After obtaining the matrix for a substring, the longest alternating subsequence length is simply the maximum value reachable from the Start state.

This gives an efficient solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(nq) O(1) Recompute longest alternating subsequence for every query
Optimal O(q log n) O(n) Segment tree storing DP transition matrices

Algorithm Walkthrough

  1. Define three DP states:
  • State 0: Start
  • State 1: Last chosen character is 'A'
  • State 2: Last chosen character is 'B'
  1. For each character, construct a 3 × 3 max-plus transition matrix.

For character 'A':

  • We may skip it, producing identity transitions.
  • We may take it if we are currently in Start or B.
  • Taking it increases the subsequence length by 1 and moves to state A.

For character 'B':

  • We may skip it.
  • We may take it if we are currently in Start or A.
  • Taking it increases the subsequence length by 1 and moves to state B.
  1. Build a segment tree.

Each leaf stores the matrix corresponding to one character. 4. Merge two child segments using max-plus matrix multiplication.

If the left segment has matrix L and the right segment has matrix R, then the parent stores:

$$L \times R$$

This exactly represents processing the left segment followed by the right segment. 5. For an update query:

  • Flip the character.
  • Replace the leaf matrix.
  • Recompute matrices on the path to the root.
  1. For a range query:
  • Retrieve the matrix product for the interval.
  • Look at row 0, which corresponds to starting from the Start state.
  • The longest alternating subsequence length is:

$$\max(M[0][0], M[0][1], M[0][2])$$ 7. Let the substring length be:

$$len = r - l + 1$$

Then the answer is:

$$len - LAS$$

Why it works

Each matrix precisely represents every valid way to either skip or take characters while maintaining the alternating constraint. Matrix multiplication composes transitions from adjacent segments, so the matrix stored for a segment exactly describes all valid alternating subsequences within that segment. Therefore, the maximum value reachable from the Start state equals the longest alternating subsequence length. Since deleting all other characters leaves such a subsequence, the minimum deletions are exactly substring_length - LAS.

Python Solution

from typing import List

class Solution:
    def minDeletions(self, s: str, queries: List[List[int]]) -> List[int]:
        NEG = -10**15

        def make_matrix(ch: str) -> List[List[int]]:
            mat = [[NEG] * 3 for _ in range(3)]

            for i in range(3):
                mat[i][i] = 0

            if ch == 'A':
                mat[0][1] = max(mat[0][1], 1)
                mat[2][1] = max(mat[2][1], 1)
            else:
                mat[0][2] = max(mat[0][2], 1)
                mat[1][2] = max(mat[1][2], 1)

            return mat

        def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            res = [[NEG] * 3 for _ in range(3)

]
            for i in range(3):
                for k in range(3):
                    if a[i][k] == NEG:
                        continue
                    aik = a[i][k]
                    for j in range(3):
                        val = aik + b[k][j]
                        if val > res[i][j]:
                            res[i][j] = val
            return res

        identity = [[NEG] * 3 for _ in range(3)]
        for i in range(3):
            identity[i][i] = 0

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

        size = 1
        while size < n:
            size <<= 1

        seg = [identity for _ in range(2 * size)]

        for i in range(n):
            seg[size + i] = make_matrix(chars[i])

        for i in range(size - 1, 0, -1):
            seg[i] = multiply(seg[i * 2], seg[i * 2 + 1])

        def update(pos: int) -> None:
            idx = size + pos
            seg[idx] = make_matrix(chars[pos])

            idx //= 2
            while idx:
                seg[idx] = multiply(seg[idx * 2], seg[idx * 2 + 1])
                idx //= 2

        def query(left: int, right: int) -> List[List[int]]:
            left += size
            right += size + 1

            left_res = identity
            right_res = identity

            while left < right:
                if left & 1:
                    left_res = multiply(left_res, seg[left])
                    left += 1

                if right & 1:
                    right -= 1
                    right_res = multiply(seg[right], right_res)

                left //= 2
                right //= 2

            return multiply(left_res, right_res)

        answer = []

        for q in queries:
            if q[0] == 1:
                pos = q[1]
                chars[pos] = 'B' if chars[pos] == 'A' else 'A'
                update(pos)
            else:
                _, l, r = q

                mat = query(l, r)
                longest = max(mat[0])

                length = r - l + 1
                answer.append(length - longest)

        return answer

Implementation Explanation

The matrix stored at each node represents the DP transitions for that segment.

The make_matrix function creates the transition matrix for a single character. Identity transitions represent skipping the character. Additional transitions represent taking the character and extending an alternating subsequence.

The multiply function performs max-plus matrix multiplication. This is the operation used to combine neighboring segments.

The segment tree stores one matrix per segment. Internal nodes are obtained by multiplying the left child matrix and the right child matrix.

For updates, we replace the leaf matrix and recompute all ancestors.

For range queries, we collect the product of all matrices in the interval. The longest alternating subsequence length is the maximum entry in row 0, since row 0 corresponds to starting from the empty state.

Finally, the answer is the substring length minus that longest subsequence length.

Go Solution

package main

func minDeletions(s string, queries [][]int) []int {
	const NEG int = -1 << 60

	multiply := func(a, b [3][3]int) [3][3]int {
		var res [3][3]int

		for i := 0; i < 3; i++ {
			for j := 0; j < 3; j++ {
				res[i][j] = NEG
			}
		}

		for i := 0; i < 3; i++ {
			for k := 0; k < 3; k++ {
				if a[i][k] == NEG {
					continue
				}
				for j := 0; j < 3; j++ {
					val := a[i][k] + b[k][j]
					if val > res[i][j] {
						res[i][j] = val
					}
				}
			}
		}

		return res
	}

	makeMatrix := func(ch byte) [3][3]int {
		var mat [3][3]int

		for i := 0; i < 3; i++ {
			for j := 0; j < 3; j++ {
				mat[i][j] = NEG
			}
			mat[i][i] = 0
		}

		if ch == 'A' {
			if 1 > mat[0][1] {
				mat[0][1] = 1
			}
			if 1 > mat[2][1] {
				mat[2][1] = 1
			}
		} else {
			if 1 > mat[0][2] {
				mat[0][2] = 1
			}
			if 1 > mat[1][2] {
				mat[1][2] = 1
			}
		}

		return mat
	}

	var identity [3][3]int
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			identity[i][j] = NEG
		}
		identity[i][i] = 0
	}

	chars := []byte(s)
	n := len(chars)

	size := 1
	for size < n {
		size <<= 1
	}

	seg := make([][3][3]int, 2*size)

	for i := range seg {
		seg[i] = identity
	}

	for i := 0; i < n; i++ {
		seg[size+i] = makeMatrix(chars[i])
	}

	for i := size - 1; i >= 1; i-- {
		seg[i] = multiply(seg[i*2], seg[i*2+1])
	}

	update := func(pos int) {
		idx := size + pos
		seg[idx] = makeMatrix(chars[pos])

		for idx >>= 1; idx > 0; idx >>= 1 {
			seg[idx] = multiply(seg[idx*2], seg[idx*2+1])
		}
	}

	query := func(l, r int) [3][3]int {
		l += size
		r += size + 1

		leftRes := identity
		rightRes := identity

		for l < r {
			if l&1 == 1 {
				leftRes = multiply(leftRes, seg[l])
				l++
			}

			if r&1 == 1 {
				r--
				rightRes = multiply(seg[r], rightRes)
			}

			l >>= 1
			r >>= 1
		}

		return multiply(leftRes, rightRes)
	}

	ans := make([]int, 0)

	for _, q := range queries {
		if q[0] == 1 {
			pos := q[1]

			if chars[pos] == 'A' {
				chars[pos] = 'B'
			} else {
				chars[pos] = 'A'
			}

			update(pos)
		} else {
			l, r := q[1], q[2]

			mat := query(l, r)

			longest := mat[0][0]
			for j := 1; j < 3; j++ {
				if mat[0][j] > longest {
					longest = mat[0][j]
				}
			}

			ans = append(ans, r-l+1-longest)
		}
	}

	return ans
}

Go-Specific Notes

The Go solution uses a fixed-size [3][3]int matrix instead of slices. Since the matrix size never changes, this avoids allocations and improves performance.

A very negative constant is used as negative infinity. All matrix multiplications are performed with max-plus arithmetic exactly as in the Python version.

Worked Examples

Example 1

Input:

s = "ABA"
queries = [[2,1,2],[1,1],[2,0,2]]

Initial string:

A B A
0 1 2

Query 1: [2,1,2]

Substring:

BA

Longest alternating subsequence length:

2

Substring length:

2

Answer:

2 - 2 = 0

Query 2: [1,1]

Flip position 1:

ABA -> AAA

Query 3: [2,0,2]

Substring:

AAA

Longest alternating subsequence:

A

Length:

1

Deletions:

3 - 1 = 2

Final answer:

[0, 2]

Example 2

Step String Query LAS Deletions
Start ABB [2,0,2] 2 ("AB") 1
Update ABA [1,2] - -
Query ABA [2,0,2] 3 0

Answer:

[1, 0]

Example 3

Step String Query LAS Deletions
Start BABA [2,0,3] 4 0
Update BBBA [1,1] - -
Query BBBA, range [1,3] = "BBA" 2 ("BA") 1

Answer:

[0, 1]

Complexity Analysis

Measure Complexity Explanation
Time O(q log n) Each update and range query performs segment tree operations
Space O(n) Segment tree stores O(n) matrices

Each segment tree node stores only a constant-size 3 × 3 matrix. Matrix multiplication therefore costs constant time. Every update and range query touches only O(log n) nodes, giving total complexity O(q log n).

Test Cases

# Example 1
assert Solution().minDeletions(
    "ABA",
    [[2, 1, 2], [1, 1], [2, 0, 2]]
) == [0, 2]  # provided example

# Example 2
assert Solution().minDeletions(
    "ABB",
    [[2, 0, 2], [1, 2], [2, 0, 2]]
) == [1, 0]  # provided example

# Example 3
assert Solution().minDeletions(
    "BABA",
    [[2, 0, 3], [1, 1], [2, 1, 3]]
) == [0, 1]  # provided example

# Single character
assert Solution().minDeletions(
    "A",
    [[2, 0, 0]]
) == [0]  # already alternating

# All same characters
assert Solution().minDeletions(
    "AAAAA",
    [[2, 0, 4]]
) == [4]  # LAS = 1

# Already alternating
assert Solution().minDeletions(
    "ABABA",
    [[2, 0, 4]]
) == [0]  # no deletions needed

# Update creates alternating string
assert Solution().minDeletions(
    "AAA",
    [[2, 0, 2], [1, 1], [2, 0, 2]]
) == [2, 0]

# Query on subrange
assert Solution().minDeletions(
    "AABBA",
    [[2, 1, 3]]
) == [1]  # "ABB" -> LAS = 2

# Multiple updates
assert Solution().minDeletions(
    "BBBB",
    [[1, 1], [1, 2], [2, 0, 3]]
) == [0]  # becomes BABA

# Entire string after several flips
assert Solution().minDeletions(
    "ABBBBA",
    [[1, 2], [1, 3], [2, 0, 5]]
) == [0]

Test Summary

Test Why
Example 1 Verifies update and query interaction
Example 2 Verifies answer changes after flip
Example 3 Verifies subrange query
Single character Smallest possible substring
All same characters Worst alternating structure
Already alternating Requires zero deletions
Update creates alternating string Checks update correctness
Query on subrange Verifies interval handling
Multiple updates Tests repeated modifications
Entire string after flips Tests combined operations

Edge Cases

Substring of Length One

A single character is always alternating because there are no adjacent characters to compare. The DP naturally returns a longest alternating subsequence length of one, producing zero deletions.

All Characters Equal

Consider "AAAAAA". Any alternating subsequence can contain only one 'A', because choosing a second 'A' would violate alternation. The matrix DP correctly computes a longest alternating subsequence length of one, so the answer becomes length - 1.

Updates That Completely Change the Structure

A flip can transform a highly repetitive string into an alternating one, or vice versa. For example:

AAA -> ABA

The segment tree recomputes all affected matrices along the update path, ensuring every future range query sees the new string state.

Querying the Entire String

Large intervals are common and may contain up to 100000 characters. The segment tree processes such queries in O(log n) time because it combines only logarithmically many precomputed matrices rather than scanning the entire interval.