3208. Alternating Groups II
Description
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 tilei
is red.colors[i] == 1
means that tilei
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.
Example 1:
Example 2:
Example 3:
Constraints:
3 <= colors.length <= 105
0 <= colors[i] <= 1
3 <= k <= colors.length
Solutions
Solution 1: Single Pass
We can unfold the ring into an array of length $2n$ and then traverse this array from left to right. We use a variable $\textit{cnt}$ to record the current length of the alternating group. If we encounter the same color, we reset $\textit{cnt}$ to $1$; otherwise, we increment $\textit{cnt}$. If $\textit{cnt} \ge k$ and the current position $i$ is greater than or equal to $n$, then we have found an alternating group, and we increment the answer by one.
After the traversal, we return the answer.
The time complexity is $O(n)$, where $n$ is the length of the array $\textit{colors}$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|