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.

Example 1:

Example 2:

Example 3:

Constraints:

• 3 <= colors.length <= 105
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

Solution

class Solution {
public:
  int numberOfAlternatingGroups(vector<int>& colors, int k) {
    int len = colors.size();
    int answer = 0;
    int count = 1;
    int last = colors[0];

    for(int i = 1; i < len + k - 1; ++i) {
      int index = i % len;
      if(colors[index] == last) {
        count = 0;
      }

      count += 1;
      if(count >= k) answer += 1;
      last = colors[index];
    }

    return answer;
  }
};

// Accepted
// 625/625 cases passed (80 ms)
// Your runtime beats 17.56 % of cpp submissions
// Your memory usage beats 61.38 % of cpp submissions (102.7 MB)