3208. Alternating Groups II

1. Extend the Array: To handle the circular nature of the array, extend the colors array by appending the first k-1 elements to its end. This allows us to easily check for alternating groups that wrap around the end of the array.

2. Initialize Counters:

   • res to store the number of alternating groups.
   • cnt to count the length of the current alternating group.

3. Iterate Through the Extended Array:

   • For each tile, check if its color is different from the previous tile.
   • If it is, increment the cnt counter.
   • If it isn't, reset the cnt counter to 1.
   • If the cnt counter reaches k, increment the res counter as it indicates the end of an alternating group.

4. Return the Result: Finally, return the res counter, which represents the number of alternating groups of length k.

Solution

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k)
    {
        for (int i = 0; i < k - 1; ++i)
        {
            colors.push_back(colors[i]);
        }

        int res = 0;

        // cnt 用來記錄長度是否達到 k
        int cnt = 1;

        for (int i = 1; i < colors.size(); ++i)
        {
            // 如果是交錯的格子，則 cnt++
            if (colors[i] != colors[i - 1])
            {
                ++cnt;
            }
            else
            {
                // 如果不是交錯的格子，則 reset cnt= 1
                cnt = 1;
            }
            // 如果 cnt 達到 k，則結果 + 1
            if (cnt >= k) ++res;
        }
        return res;        
    }
};

• 時間複雜度：
  $O(n+k-1)$
• 空間複雜度：
  $O(n+k)$