# [LeetCode] 3208. Alternating Groups II

## Problem

[https://leetcode.com/problems/alternating-groups-ii/description](https://leetcode.com/problems/alternating-groups-ii/description/?envType=daily-question&envId=2025-03-09)

**Leetcode** - Alternating Groups II

**Type** - Two pointers, Sliding Window

**Difficulty** - Medium

## **Approach & Solution**

`n * k` solution will exceed time limit.

Instead, if we get alternating segment \[l, r), we can get r - l - k + 1 groups.

**data structure and variables:**

* `last`: number of last index
    

* `ans`: total counts of alternating groups
    

With sliding window approach, increase right range as long as possible.

After increasing right range, `[l, r)` will be alternating segment.

Increase `ans` by `r - l - k + 1` if `r-l >= k`.

Then, update `l` to `r`.

## Complexity

**Time Complexity**: `O(N)` - Iterating `0` to `n+k-1`

**Space Complexity**: `O(1)` - No extra data structures.

## Code (C++ | Go)

```cpp
#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k) {
        int n = colors.size();

        int ans = 0;
        for(int i = 0; i < n+k-1; i++) {
            int last = colors[i%n];
            int j = i+1;
            while(j < n+k-1 && colors[j%n] != last) {
                last = colors[j%n];
                j++;
            } 

            if(j - i >= k) {
                ans += j-i-k+1;
            }
            i = j - 1;
        }

        return ans;
    }
};
```

```go
func numberOfAlternatingGroups(colors []int, k int) int {
    ans := 0
    n := len(colors)

    for i := 0; i < n+k-1; i++ {
        last := colors[i%n]
        j := i+1
        for j < n+k-1 && colors[j%n] != last {
            last = colors[j%n] 
            j++
        }

        if j - i >= k {
            ans += j - i - k + 1;
        } 
        i = j-1;
    }

    return ans
}
```