Show problems as
Classic problem #3208MediumArraySliding Window

Alternating Groups II

Real-world version: Alternating Windows on the Carousel
Tracked in this browser only
Read Alternating Groups II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A fairground carousel has cushions bolted all the way round its rim, numbered 0 upward in the direction it turns. The rim closes on itself, so the last cushion sits right beside cushion 0. cushions[i] is 0 when cushion i is plain and 1 when it is striped.

A window is k cushions taken in turning order from some starting cushion, carrying on past the last cushion and round to cushion 0 whenever it has to. Every cushion starts one window, so the rim has exactly cushions.length windows and two windows are different whenever they start at different cushions.

A window is alternating when no two cushions that sit side by side inside it carry the same pattern.

Return how many of the rim's windows are alternating.

Examples

Example 1

Input
cushions = [0, 1, 0, 1], k = 3
Output
4

Patterns swap at every step all the way round, including across the seam between the last cushion and cushion 0, so each of the four windows of three has no matching neighbours inside it.

Example 2

Input
cushions = [0, 1, 0, 0, 1, 1], k = 3
Output
2

The window starting at cushion 0 reads plain, striped, plain. The window starting at cushion 5 runs striped, plain, striped by carrying on past the seam. Every other window contains a matching pair.

Example 3

Input
cushions = [0, 0, 0], k = 3
Output
0

Every cushion is plain, so any two side by side match and no window qualifies.

Example 4

Input
cushions = [0, 1, 0, 1], k = 4
Output
4

Each window now covers the whole rim from a different starting cushion, and all four of them alternate throughout.

Example 5

Input
cushions = [0, 1, 0], k = 3
Output
1

The rim has an odd number of cushions, so the last cushion and cushion 0 are both plain. Only the window that starts at cushion 0 avoids having those two side by side.

Constraints

  • 3 <= cushions.length <= 10^5
  • 0 <= cushions[i] <= 1
  • 3 <= k <= cushions.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def number_of_alternating_groups(cushions: list[int], k: int) -> int:
Java
public int numberOfAlternatingGroups(int[] cushions, int k)

More on the same topics