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] == 0means that tileiis red.colors[i] == 1means that tileiis blue.
An alternating group is every k contiguous tiles in the circle with alternating colors, where 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
Input
colors = [0,1,0,1,0], k = 3Output
3The three length-3 circular groups starting at indices 0, 1, and 2 have alternating colors.
Example 2
Input
colors = [0,1,0,0,1,0,1], k = 6Output
2Only the two length-6 circular groups starting at indices 3 and 4 have alternating colors.
Constraints
- 3 <= colors.length <= 10^5
- 0 <= colors[i] <= 1
- 3 <= k <= colors.length