[LeetCode] Alternating Groups II

3208. Alternating Groups II

There is a circle of red and blue tiles. You are given an array of integers colors and an integer k. The color of tile i is represented by colors[i]:

  • colors[i] == 0 means that tile i is red.
  • colors[i] == 1 means that tile i is blue.

An alternating group is every k contiguous tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its left and right tiles).

Return the number of alternating groups.

Note that since colors represents a circle, the first and the last tiles are considered to be next to each other.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& A, int k) {
int res = 0, n = A.size();
for(int i = 0; i < k - 1; i++) A.push_back(A[i]);
int l = 0, r = 0;
while(l < n) {
int fl = A[l];
while(r < A.size() and A[r] == fl) {
r++;
fl = !fl;
}
res += max(0,(r - l + 1) - k);
l = r;
}
return res;
}
};

Author: Song Hayoung
Link: https://songhayoung.github.io/2024/07/07/PS/LeetCode/alternating-groups-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.