3208. Alternating Groups II

leetcode

  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.

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;
    }
};
  • T: O(N+K−1)O(N + K - 1)
  • S: O(N+K)O(N + K)