Count Alternating Groups around a Circle
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The array `colors` describes tiles arranged in a circle: `0` denotes a red tile and `1` denotes a blue tile. You are also given an integer `k`.
A group consists of `k` consecutive tiles around the circle. It is alternating when every two consecutive tiles within that group have different colors. Equivalently, each tile except the group's first and last has a different color from both of its neighbors within the group.
Return the number of alternating groups. The last tile of the array is adjacent to the first tile, so a group may cross that boundary.
```cpp
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k);
};
```
### Examples
**Example 1:**
```text
Input: colors = [1,0,1,0], k = 3
Output: 4
Explanation: The groups starting at indices 0, 1, 2, and 3 all alternate, including the groups that cross the end of the array.
```
**Example 2:**
```text
Input: colors = [0,0,1,0,1], k = 4
Output: 2
Explanation: Start at index 1 to obtain [0,1,0,1], or at index 2 to obtain [1,0,1,0]. Every other starting index gives a group containing equal consecutive colors.
```
### Constraints
- `3 <= colors.length <= 100000`.
- Each `colors[i]` is either `0` or `1`.
- `3 <= k <= colors.length`.
### Clarifying Questions
- Can groups overlap? Yes.
- Do groups with the same color sequence count separately? Yes, if their starting positions differ.
- How far may a group wrap? It contains exactly `k` tiles, with `k` no larger than the number of tiles in the circle.
- Must the group's last tile differ from its first tile? That pair is not an extra comparison. Check only consecutive pairs inside the chosen sequence of `k` tiles.
### What a Strong Answer Covers
- Counts groups by their starting positions without duplicating a group.
- Applies the color rule to exactly the tiles belonging to each group, including wrapped groups.
- Handles a completely alternating circle, equal neighboring tiles, and `k` equal to the circle size.
```hint Track consecutive alternation
Consider the length of the alternating run ending at a tile while reading around the circle. Decide how far beyond the original array a conceptual scan must extend to include every starting position once.
```
Overview: Count groups of k alternating red and blue tiles around a circle. Include groups that cross the array boundary and count different starting positions separately.
