Alternating Groups II
Source: leetcode
Difficulty: Medium
Tags: array, sliding-window

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:**



**Input:** colors \= \[0,1,0,1,0], k \= 3


**Output:** 3


**Explanation:**


**![](https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183519.png)**


Alternating groups:


![](https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182448.png)![](https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182844.png)![](https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-183057.png)



**Example 2:**



**Input:** colors \= \[0,1,0,0,1,0,1], k \= 6


**Output:** 2


**Explanation:**


**![](https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183907.png)**


Alternating groups:


![](https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184128.png)![](https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184240.png)



**Example 3:**



**Input:** colors \= \[1,1,0,1], k \= 4


**Output:** 0


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184516.png)



 


**Constraints:**


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




C++ solution:
#pragma gcc optimize("03")
auto init = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();
class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k) {
        int window = 1 , ans =0 , n =colors.size();
        for(int i = 1; i<n-1+k ; i++ ){
            if(colors[i%n]!=colors[(i-1+n)%n]){
                window++;
            }   
            else{
                window = 1;
            }
            if(window>=k)ans++;
        }
        return ans;
    }
};

Go solution:
func numberOfAlternatingGroups(colors []int, k int) int {
	count := 1
	colors = append(colors, colors[:k-1]...)
    l := 1
    res := 0
	for l < len(colors) {
		if colors[l] != colors[l-1] {
            count++
		} else {
			count = 1
		}
        if count >= k{
            res++
        }
        l++
	}

	return res
}

Java solution:
class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
        int[] extendedColors = new int[n + k - 1];
        System.arraycopy(colors, 0, extendedColors, 0, n);
        System.arraycopy(colors, 0, extendedColors, n, k - 1);
        int res = 0;
        int cnt = 1;
        for (int i = 1; i < extendedColors.length; ++i) {
            if (extendedColors[i] != extendedColors[i - 1]) ++cnt;
            else cnt = 1;
            if (cnt >= k) ++res;
        }     
        return res;
    }
}

JavaScript solution:
/**
 * @param {number[]} colors
 * @param {number} k
 * @return {number}
 */
var numberOfAlternatingGroups = function (colors, k) {
    for (var i = 0; i < k - 1; ++i) colors.push(colors[i]);
    var res = 0;
    var cnt = 1;
    for (var i = 1; i < colors.length; ++i) {
        if (colors[i] !== colors[i - 1]) ++cnt;
        else cnt = 1;
        if (cnt >= k) ++res;
    }
    return res;
};

Python solution:
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        
        idx = None
        
        for i in range(n - 1):
            if colors[i] == colors[i + 1]:
                idx = i + 1
                
                break
                
        if idx == None: 
            if colors[0] != colors[-1]:
                return n 
            
            else: 
                return max(n - k + 1, 0)
            
        
        colors = colors[idx: ] + colors[: idx]
        
        prev = 0 
        cnt = 0

        ans = 0 
        
        for color in colors + [colors[-1]]: 
            if color != prev: 
                cnt += 1

            else: 
                if cnt >= k: 
                    ans += (cnt - k + 1)

                cnt = 1 

            prev = color 

        return ans

Ruby solution:
def number_of_alternating_groups(colors, k)
    n = colors.size
    window = 1
    ans = 0
    max_i = n + k - 2
    (1..max_i).each do |i|
        current = i % n
        prev = (i - 1) % n
        if colors[current] != colors[prev]
            window += 1
        else
            window = 1
        end
        ans += 1 if window >= k
    end
    ans
end