3245. Alternating Groups III Hard

1/**
2 * [3245] Alternating Groups III
3 *
4 * There are some red and blue tiles arranged circularly. You are given an array of integers colors and a 2D integers array queries.
5 * The color of tile i is represented by colors[i]:
6 * 
7 * 	colors[i] == 0 means that tile i is red.
8 * 	colors[i] == 1 means that tile i is blue.
9 * 
10 * An alternating group is a contiguous subset of tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its adjacent tiles in the group).
11 * You have to process queries of two types:
12 * 
13 * 	queries[i] = [1, sizei], determine the count of alternating groups with size sizei.
14 * 	queries[i] = [2, indexi, colori], change colors[indexi] to color<font face="monospace">i</font>.
15 * 
16 * Return an array answer containing the results of the queries of the first type in order.
17 * Note that since colors represents a circle, the first and the last tiles are considered to be next to each other.
18 *  
19 * <strong class="example">Example 1:
20 * <div class="example-block">
21 * Input: <span class="example-io">colors = [0,1,1,0,1], queries = [[2,1,0],[1,4]]</span>
22 * Output: <span class="example-io">[2]</span>
23 * Explanation:
24 * <strong class="example"><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-14-44.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" />
25 * First query:
26 * Change colors[1] to 0.
27 * <img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-20-25.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" />
28 * Second query:
29 * Count of the alternating groups with size 4:
30 * <img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-25-02-2.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-24-12.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" />
31 * </div>
32 * <strong class="example">Example 2:
33 * <div class="example-block">
34 * Input: <span class="example-io">colors = [0,0,1,0,1,1], queries = [[1,3],[2,3,0],[1,5]]</span>
35 * Output: <span class="example-io">[2,0]</span>
36 * Explanation:
37 * <img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-35-50.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" />
38 * First query:
39 * Count of the alternating groups with size 3:
40 * <img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-37-13.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-36-40.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" />
41 * Second query: colors will not change.
42 * Third query: There is no alternating group with size 5.
43 * </div>
44 *  
45 * Constraints:
46 * 
47 * 	4 <= colors.length <= 5 * 10^4
48 * 	0 <= colors[i] <= 1
49 * 	1 <= queries.length <= 5 * 10^4
50 * 	queries[i][0] == 1 or queries[i][0] == 2
51 * 	For all i that:
52 * 	
53 * 		queries[i][0] == 1: queries[i].length == 2, 3 <= queries[i][1] <= colors.length - 1
54 * 		queries[i][0] == 2: queries[i].length == 3, 0 <= queries[i][1] <= colors.length - 1, 0 <= queries[i][2] <= 1
55 * 	
56 * 	
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/alternating-groups-iii/
62// discuss: https://leetcode.com/problems/alternating-groups-iii/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn number_of_alternating_groups(colors: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
68        vec![]
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_3245() {
80    }
81}
82