This problem asks for the longest possible streak of sunny days after correcting exactly one wrong record. Each day is either S for sunshine or P for precipitation.

The important detail is that exactly one day is wrong. If there is a P, changing it to S may connect a sunny block on the left with a sunny block on the right. If every day is already S, we must change one S to P, so the answer becomes N - 1.

What the Problem Is Asking

We are given N days of weather records. Each record is one of:

• S: sunshine
• P: precipitation

Exactly one record is wrong. We must change exactly one day, either:

• P -> S
• or S -> P

After that correction, we want the maximum possible length of a consecutive streak of S.

For example:

S S S P S S
      ^

If we change the middle P into S, the two sunny blocks join together, giving a streak of 6 sunny days.

Where Beginners Often Get Stuck

A common first attempt is to count the longest streak that already appears:

best = 0
cur = 0
for day in days:
    if day == "S":
        cur += 1
        best = max(best, cur)
    else:
        cur = 0

That only answers: what is the longest sunny streak in the original record?

But this problem asks: what is the longest sunny streak after fixing one wrong day?

There is also one important edge case. If the input is already all sunny:

S S S S S

we still have to change exactly one day. So the best answer is not 5; it is 4.

Core Algorithm Idea

There are two natural ways to understand this problem:

• prefix/suffix consecutive counts
• sliding window with at most one P

This article uses the prefix/suffix approach because it makes the merge idea very visible.

The prefix/suffix approach precomputes:

left[i]  = number of consecutive S ending at i
right[i] = number of consecutive S starting at i

Then for every P at index i, the streak created by changing it to S is:

left[i - 1] + 1 + right[i + 1]

with boundary checks at the first and last positions.

In words: left sunny block, plus the corrected day, plus right sunny block.

State Definition

Suppose the weather record is:

S S P S S S P

The left array stores the length of the sunny streak ending at each position:

days:  S S P S S S P
left:  1 2 0 1 2 3 0

The right array stores the length of the sunny streak starting at each position:

days:   S S P S S S P
right:  2 1 0 3 2 1 0

Now look at the P at index 2:

S S P S S S
    ^

If we change it to S, the candidate answer is:

left[1] + 1 + right[3] = 2 + 1 + 3 = 6

Algorithm Steps

1. Read N and the N weather records.
2. Count whether there is any P.
3. Build left from left to right.
4. Build right from right to left.
5. Try changing every P into S.
6. If there is no P, output N - 1.
7. Otherwise, output the best merged streak.

Python Solution

N = int(input())
days = [input().strip() for _ in range(N)]

count_p = days.count("P")

left = [0] * N
for i in range(N):
    if days[i] == "S":
        left[i] = 1 + (left[i - 1] if i > 0 else 0)

right = [0] * N
for i in range(N - 1, -1, -1):
    if days[i] == "S":
        right[i] = 1 + (right[i + 1] if i < N - 1 else 0)

best = 0

for i in range(N):
    if days[i] == "P":
        left_block = left[i - 1] if i > 0 else 0
        right_block = right[i + 1] if i < N - 1 else 0
        best = max(best, left_block + 1 + right_block)

if count_p == 0:
    print(N - 1)
else:
    print(best)

C++ Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<char> days(N);
    for (int i = 0; i < N; i++) {
        cin >> days[i];
    }

    int countP = 0;
    for (char day : days) {
        if (day == 'P') countP++;
    }

    vector<int> left(N, 0), right(N, 0);

    for (int i = 0; i < N; i++) {
        if (days[i] == 'S') {
            left[i] = 1 + (i > 0 ? left[i - 1] : 0);
        }
    }

    for (int i = N - 1; i >= 0; i--) {
        if (days[i] == 'S') {
            right[i] = 1 + (i < N - 1 ? right[i + 1] : 0);
        }
    }

    int best = 0;
    for (int i = 0; i < N; i++) {
        if (days[i] == 'P') {
            int leftBlock = (i > 0) ? left[i - 1] : 0;
            int rightBlock = (i < N - 1) ? right[i + 1] : 0;
            best = max(best, leftBlock + 1 + rightBlock);
        }
    }

    if (countP == 0) {
        cout << N - 1 << "\n";
    } else {
        cout << best << "\n";
    }

    return 0;
}

Complexity Analysis

We scan the list three times:

• once to build left
• once to build right
• once to try every P

The time complexity is:

O(N)

The memory complexity is:

O(N)

A sliding window solution can also solve this in O(N) time with O(1) extra memory, but prefix/suffix arrays are often easier for students to understand first.

Common Mistakes

1. Forgetting that we must change exactly one day, so all-sunny input returns N - 1.
2. Only counting the original longest sunny streak.
3. Accessing left[i - 1] or right[i + 1] without boundary checks.
4. Misunderstanding left[i]: it means the sunny streak ending at i, not the total number of sunny days to the left.
5. Using nested loops to count left and right streaks from scratch for every position, which can become O(N^2).

Review Questions

1. Why do we usually focus on changing P to S?
2. What do left[i] and right[i] represent?
3. Why does the formula use left[i - 1] + 1 + right[i + 1]?
4. Why is the answer N - 1 when every day is already sunny?
5. Can you write the same solution using a sliding window?