3777. Minimum Deletions to Make Alternating Substring Hard

1/**
2 * [3777] Minimum Deletions to Make Alternating Substring
3 *
4 * You are given a string s of length n consisting only of the characters 'A' and 'B'.
5 * You are also given a 2D integer array queries of length q, where each queries[i] is one of the following:
6 * 
7 * 	[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.
8 * 	[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.
9 * 
10 * A <span data-keyword="substring-nonempty">substring</span> is alternating if no two adjacent characters are equal. A substring of length 1 is always alternating.
11 * Return an integer array answer, where answer[i] is the result of the i^th query of type [2, l, r].
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">s = "ABA", queries = [[2,1,2],[1,1],[2,0,2]]</span>
16 * Output: <span class="example-io">[0,2]</span>
17 * Explanation:
18 * <table style="border: 1px solid black;">
19 * 	<thead>
20 * 		<tr>
21 * 			<th align="center" style="border: 1px solid black;">i</th>
22 * 			<th align="center" style="border: 1px solid black;">queries[i]</th>
23 * 			<th align="center" style="border: 1px solid black;">j</th>
24 * 			<th align="center" style="border: 1px solid black;">l</th>
25 * 			<th align="center" style="border: 1px solid black;">r</th>
26 * 			<th align="center" style="border: 1px solid black;">s before query</th>
27 * 			<th align="center" style="border: 1px solid black;">s[l..r]</th>
28 * 			<th align="center" style="border: 1px solid black;">Result</th>
29 * 			<th align="center" style="border: 1px solid black;">Answer</th>
30 * 		</tr>
31 * 	</thead>
32 * 	<tbody>
33 * 		<tr>
34 * 			<td align="center" style="border: 1px solid black;">0</td>
35 * 			<td align="center" style="border: 1px solid black;">[2, 1, 2]</td>
36 * 			<td align="center" style="border: 1px solid black;">-</td>
37 * 			<td align="center" style="border: 1px solid black;">1</td>
38 * 			<td align="center" style="border: 1px solid black;">2</td>
39 * 			<td align="center" style="border: 1px solid black;">"ABA"</td>
40 * 			<td align="center" style="border: 1px solid black;">"BA"</td>
41 * 			<td align="center" style="border: 1px solid black;">Already alternating</td>
42 * 			<td align="center" style="border: 1px solid black;">0</td>
43 * 		</tr>
44 * 		<tr>
45 * 			<td align="center" style="border: 1px solid black;">1</td>
46 * 			<td align="center" style="border: 1px solid black;">[1, 1]</td>
47 * 			<td align="center" style="border: 1px solid black;">1</td>
48 * 			<td align="center" style="border: 1px solid black;">-</td>
49 * 			<td align="center" style="border: 1px solid black;">-</td>
50 * 			<td align="center" style="border: 1px solid black;">"ABA"</td>
51 * 			<td align="center" style="border: 1px solid black;">-</td>
52 * 			<td align="center" style="border: 1px solid black;">Flip s[1] from 'B' to 'A'</td>
53 * 			<td align="center" style="border: 1px solid black;">-</td>
54 * 		</tr>
55 * 		<tr>
56 * 			<td align="center" style="border: 1px solid black;">2</td>
57 * 			<td align="center" style="border: 1px solid black;">[2, 0, 2]</td>
58 * 			<td align="center" style="border: 1px solid black;">-</td>
59 * 			<td align="center" style="border: 1px solid black;">0</td>
60 * 			<td align="center" style="border: 1px solid black;">2</td>
61 * 			<td align="center" style="border: 1px solid black;">"AAA"</td>
62 * 			<td align="center" style="border: 1px solid black;">"AAA"</td>
63 * 			<td align="center" style="border: 1px solid black;">Delete any two 'A's to get "A"</td>
64 * 			<td align="center" style="border: 1px solid black;">2</td>
65 * 		</tr>
66 * 	</tbody>
67 * </table>
68 * Thus, the answer is [0, 2].
69 * </div>
70 * <strong class="example">Example 2:
71 * <div class="example-block">
72 * Input: <span class="example-io">s = "ABB", queries = [[2,0,2],[1,2],[2,0,2]]</span>
73 * Output: <span class="example-io">[1,0]</span>
74 * Explanation:
75 * <table style="border: 1px solid black;">
76 * 	<thead>
77 * 		<tr>
78 * 			<th align="center" style="border: 1px solid black;">i</th>
79 * 			<th align="center" style="border: 1px solid black;">queries[i]</th>
80 * 			<th align="center" style="border: 1px solid black;">j</th>
81 * 			<th align="center" style="border: 1px solid black;">l</th>
82 * 			<th align="center" style="border: 1px solid black;">r</th>
83 * 			<th align="center" style="border: 1px solid black;">s before query</th>
84 * 			<th align="center" style="border: 1px solid black;">s[l..r]</th>
85 * 			<th align="center" style="border: 1px solid black;">Result</th>
86 * 			<th align="center" style="border: 1px solid black;">Answer</th>
87 * 		</tr>
88 * 	</thead>
89 * 	<tbody>
90 * 		<tr>
91 * 			<td align="center" style="border: 1px solid black;">0</td>
92 * 			<td align="center" style="border: 1px solid black;">[2, 0, 2]</td>
93 * 			<td align="center" style="border: 1px solid black;">-</td>
94 * 			<td align="center" style="border: 1px solid black;">0</td>
95 * 			<td align="center" style="border: 1px solid black;">2</td>
96 * 			<td align="center" style="border: 1px solid black;">"ABB"</td>
97 * 			<td align="center" style="border: 1px solid black;">"ABB"</td>
98 * 			<td align="center" style="border: 1px solid black;">Delete one 'B' to get "AB"</td>
99 * 			<td align="center" style="border: 1px solid black;">1</td>
100 * 		</tr>
101 * 		<tr>
102 * 			<td align="center" style="border: 1px solid black;">1</td>
103 * 			<td align="center" style="border: 1px solid black;">[1, 2]</td>
104 * 			<td align="center" style="border: 1px solid black;">2</td>
105 * 			<td align="center" style="border: 1px solid black;">-</td>
106 * 			<td align="center" style="border: 1px solid black;">-</td>
107 * 			<td align="center" style="border: 1px solid black;">"ABB"</td>
108 * 			<td align="center" style="border: 1px solid black;">-</td>
109 * 			<td align="center" style="border: 1px solid black;">Flip s[2] from 'B' to 'A'</td>
110 * 			<td align="center" style="border: 1px solid black;">-</td>
111 * 		</tr>
112 * 		<tr>
113 * 			<td align="center" style="border: 1px solid black;">2</td>
114 * 			<td align="center" style="border: 1px solid black;">[2, 0, 2]</td>
115 * 			<td align="center" style="border: 1px solid black;">-</td>
116 * 			<td align="center" style="border: 1px solid black;">0</td>
117 * 			<td align="center" style="border: 1px solid black;">2</td>
118 * 			<td align="center" style="border: 1px solid black;">"ABA"</td>
119 * 			<td align="center" style="border: 1px solid black;">"ABA"</td>
120 * 			<td align="center" style="border: 1px solid black;">Already alternating</td>
121 * 			<td align="center" style="border: 1px solid black;">0</td>
122 * 		</tr>
123 * 	</tbody>
124 * </table>
125 * Thus, the answer is [1, 0].
126 * </div>
127 * <strong class="example">Example 3:
128 * <div class="example-block">
129 * Input: <span class="example-io">s = "BABA", queries = [[2,0,3],[1,1],[2,1,3]]</span>
130 * Output: <span class="example-io">[0,1]</span>
131 * Explanation:
132 * <table style="border: 1px solid black;">
133 * 	<thead>
134 * 		<tr>
135 * 			<th align="center" style="border: 1px solid black;">i</th>
136 * 			<th align="center" style="border: 1px solid black;">queries[i]</th>
137 * 			<th align="center" style="border: 1px solid black;">j</th>
138 * 			<th align="center" style="border: 1px solid black;">l</th>
139 * 			<th align="center" style="border: 1px solid black;">r</th>
140 * 			<th align="center" style="border: 1px solid black;">s before query</th>
141 * 			<th align="center" style="border: 1px solid black;">s[l..r]</th>
142 * 			<th align="center" style="border: 1px solid black;">Result</th>
143 * 			<th align="center" style="border: 1px solid black;">Answer</th>
144 * 		</tr>
145 * 	</thead>
146 * 	<tbody>
147 * 		<tr>
148 * 			<td align="center" style="border: 1px solid black;">0</td>
149 * 			<td align="center" style="border: 1px solid black;">[2, 0, 3]</td>
150 * 			<td align="center" style="border: 1px solid black;">-</td>
151 * 			<td align="center" style="border: 1px solid black;">0</td>
152 * 			<td align="center" style="border: 1px solid black;">3</td>
153 * 			<td align="center" style="border: 1px solid black;">"BABA"</td>
154 * 			<td align="center" style="border: 1px solid black;">"BABA"</td>
155 * 			<td align="center" style="border: 1px solid black;">Already alternating</td>
156 * 			<td align="center" style="border: 1px solid black;">0</td>
157 * 		</tr>
158 * 		<tr>
159 * 			<td align="center" style="border: 1px solid black;">1</td>
160 * 			<td align="center" style="border: 1px solid black;">[1, 1]</td>
161 * 			<td align="center" style="border: 1px solid black;">1</td>
162 * 			<td align="center" style="border: 1px solid black;">-</td>
163 * 			<td align="center" style="border: 1px solid black;">-</td>
164 * 			<td align="center" style="border: 1px solid black;">"BABA"</td>
165 * 			<td align="center" style="border: 1px solid black;">-</td>
166 * 			<td align="center" style="border: 1px solid black;">Flip s[1] from 'A' to 'B'</td>
167 * 			<td align="center" style="border: 1px solid black;">-</td>
168 * 		</tr>
169 * 		<tr>
170 * 			<td align="center" style="border: 1px solid black;">2</td>
171 * 			<td align="center" style="border: 1px solid black;">[2, 1, 3]</td>
172 * 			<td align="center" style="border: 1px solid black;">-</td>
173 * 			<td align="center" style="border: 1px solid black;">1</td>
174 * 			<td align="center" style="border: 1px solid black;">3</td>
175 * 			<td align="center" style="border: 1px solid black;">"BBBA"</td>
176 * 			<td align="center" style="border: 1px solid black;">"BBA"</td>
177 * 			<td align="center" style="border: 1px solid black;">Delete one 'B' to get "BA"</td>
178 * 			<td align="center" style="border: 1px solid black;">1</td>
179 * 		</tr>
180 * 	</tbody>
181 * </table>
182 * Thus, the answer is [0, 1].
183 * </div>
184 *  
185 * Constraints:
186 * 
187 * 	1 <= n == s.length <= 10^5
188 * 	s[i] is either 'A' or 'B'.
189 * 	1 <= q == queries.length <= 10^5
190 * 	queries[i].length == 2 or 3
191 * 	
192 * 		queries[i] == [1, j] or,
193 * 		queries[i] == [2, l, r]
194 * 		0 <= j <= n - 1
195 * 		0 <= l <= r <= n - 1
196 * 	
197 * 	
198 * 
199 */
200pub struct Solution {}
201
202// problem: https://leetcode.com/problems/minimum-deletions-to-make-alternating-substring/
203// discuss: https://leetcode.com/problems/minimum-deletions-to-make-alternating-substring/discuss/?currentPage=1&orderBy=most_votes&query=
204
205// submission codes start here
206
207impl Solution {
208    pub fn min_deletions(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
209        vec![]
210    }
211}
212
213// submission codes end
214
215#[cfg(test)]
216mod tests {
217    use super::*;
218
219    #[test]
220    fn test_3777() {
221    }
222}
223