690. Stretches Holding Exactly k Odd Numbers

Count the CONTIGUOUS stretches of the array that contain exactly k odd numbers.

1 1 2 1 1, k = 3 -> 2 2 4 6, k = 1 -> 0 1, k = 0 -> 0 2, k = 0 -> 1

## Why a window cannot count "exactly" directly

A sliding window works when the condition is MONOTONE: growing the window can only make it worse and shrinking can only make it better. "At most k odd numbers" is like that. "Exactly k" is not, because growing can take you from too few to correct to too many.

So there is no single window that can be grown and shrunk to count exact matches.

## Two at-most sweeps

exactly(k) = atMost(k) - atMost(k - 1)

Every stretch with at most k odd numbers either has at most k-1, or has exactly k. Subtracting removes the first group and leaves the second.

This is the same move as problem 644 in the two-pointers topic, where a band was counted as a difference of two boundary counts. Turning "exactly" or "between" into a difference of "at most" counts is one of the most reusable ideas in the whole subject.

## The at-most sweep

lo = 0, odd = 0, c = 0 for hi in 0 .. n-1: if a[hi] is odd: odd += 1 while odd > k: if a[lo] is odd: odd -= 1; lo += 1 c += hi - lo + 1

Counting the windows that END at each position is what makes this a count rather than a maximum.

## The k = 0 case

atMost(-1) must be 0: no stretch can contain a negative number of odd values, not even the empty one, because the sweep only counts non-empty stretches.

Returning 0 for a negative argument is the one line that makes k = 0 work, and 1 with k = 0 answering 0 while 2 with k = 0 answers 1 are the two tests for it.

## Overflow

With 200000 even numbers and k = 0, every stretch qualifies and the answer is C(200001, 2), about 2 * 10^10. The count needs 64 bits.

## Cost

Time O(n), two passes. Space O(1).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ n` - `1 ≤ each value ≤ 10^9`