Overview

Given a weather forecast for \(N\) days, the problem asks to choose a consecutive \(K\)-day period and maximize the number of sunny days within it. This can be solved efficiently using the sliding window technique.

Analysis

Naive Approach and Its Issues

The simplest method is to count the number of sunny days from day \(d\) to day \(d + K - 1\) for every possible starting day \(d\) (\(1 \leq d \leq N - K + 1\)).

• There are \(N - K + 1\) candidate starting days
• For each candidate, we count \(K\) days

In this case, the time complexity is \(O((N - K + 1) \times K)\), which is \(O(N^2)\) in the worst case. Since \(N\) can be up to \(10^6\), this would require around \(10^{12}\) operations, resulting in TLE (Time Limit Exceeded).

Key Observation

When we shift the window of \(K\) consecutive days by one day, the only changes are that one day is removed from the left end and one day is added to the right end.

For example, with \(N = 7, K = 3\) and the weather being S C S S R S C:

Window	Days	Sunny count	Change
Days 1–3	S C S	2	Initial value
Days 2–4	C S S	2	Day 1’s S is removed, Day 4’s S is added
Days 3–5	S S R	2	Day 2’s C is removed, Day 5’s R is added

In this way, by updating only the difference from the previous interval’s sunny count, each step can be computed in \(O(1)\).

Algorithm

We use the sliding window technique (a method that slides a fixed-length interval one position at a time).

1. Create an array sunny by converting each day’s weather to \(1\) if sunny, \(0\) otherwise.
2. Calculate the number of sunny days current in the first window (day 1 through day \(K\)).
3. Slide the window one day to the right at a time:
   • Add the value sunny[i] of the new day entering from the right end.
   • Subtract the value sunny[i - K] of the day leaving from the left end.
   • If current exceeds the current maximum best, update it.
4. The final best is the answer.

current += sunny[i] - sunny[i - K]

The key point is that this single line of updating always correctly maintains the number of sunny days within the window.

Complexity

• Time complexity: \(O(N)\) — \(O(N)\) for creating the array, \(O(N)\) for the sliding window traversal
• Space complexity: \(O(N)\) — for the sunny array that converts the weather to 0/1

This runs sufficiently fast even for \(N = 10^6\).

Implementation Notes

• By converting the weather string to an integer array of 1/0 in advance, the window update becomes simple addition and subtraction, making the code concise.

• Structuring the solution in two stages — computing the initial window sum with sum(sunny[:K]) and then performing incremental updates in a loop — helps prevent bugs.

• Using a direct comparison if current > best instead of max(best, current) avoids function call overhead for faster execution (this can make a difference when \(N\) is large).

  Source Code

N, K = map(int, input().split())
W = input().split()

sunny = [1 if w == 'S' else 0 for w in W]

current = sum(sunny[:K])
best = current

for i in range(K, N):
    current += sunny[i] - sunny[i - K]
    if current > best:
        best = current

print(best)

---

This editorial was generated by claude4.6opus-thinking.