Description
Description
Editorial
Editorial
Solutions
Solutions
Submissions
Submissions
3777. Minimum Deletions to Make Alternating Substring
Hard

You are given a string s of length n consisting only of the characters 'A' and 'B'.

You are also given a 2D integer array queries of length q, where each queries[i] is one of the following:

  • [1, j]: Flip the character at index j of s i.e. 'A' changes to 'B' (and vice versa). This operation mutates s and affects subsequent queries.
  • [2, l, r]: Compute the minimum number of character deletions required to make the substring s[l..r] alternating. This operation does not modify s; the length of s remains n.

A is alternating if no two adjacent characters are equal. A substring of length 1 is always alternating.

Return an integer array answer, where answer[i] is the result of the ith query of type [2, l, r].

 

Example 1:

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

Output: [0,2]

Explanation:

iqueries[i]jlrs before querys[l..r]ResultAnswer
0[2, 1, 2]-12"ABA""BA"Already alternating0
1[1, 1]1--"ABA"-Flip s[1] from 'B' to 'A'-
2[2, 0, 2]-02"AAA""AAA"Delete any two 'A's to get "A"2

Thus, the answer is [0, 2].

Example 2:

Input: s = "ABB", queries = [[2,0,2],[1,2],[2,0,2]]

Output: [1,0]

Explanation:

iqueries[i]jlrs before querys[l..r]ResultAnswer
0[2, 0, 2]-02"ABB""ABB"Delete one 'B' to get "AB"1
1[1, 2]2--"ABB"-Flip s[2] from 'B' to 'A'-
2[2, 0, 2]-02"ABA""ABA"Already alternating0

Thus, the answer is [1, 0].

Example 3:

Input: s = "BABA", queries = [[2,0,3],[1,1],[2,1,3]]

Output: [0,1]

Explanation:

iqueries[i]jlrs before querys[l..r]ResultAnswer
0[2, 0, 3]-03"BABA""BABA"Already alternating0
1[1, 1]1--"BABA"-Flip s[1] from 'A' to 'B'-
2[2, 1, 3]-13"BBBA""BBA"Delete one 'B' to get "BA"1

Thus, the answer is [0, 1].

 

Constraints:

  • 1 <= n == s.length <= 105
  • s[i] is either 'A' or 'B'.
  • 1 <= q == queries.length <= 105
  • queries[i].length == 2 or 3
    • queries[i] == [1, j] or,
    • queries[i] == [2, l, r]
    • 0 <= j <= n - 1
    • 0 <= l <= r <= n - 1
 
Code
Code
Testcase
Testcase
Test Result
Test Result