1065. When to Close the Shop

A shop is open for m hours. For each hour you are told whether a customer came, Y, or not, N. You choose an hour j at which to close, from 0 to m; the shop is then open for hours 0 to j - 1 and shut from hour j onwards.

The penalty is the number of hours the shop is OPEN with no customer, plus the number of hours it is SHUT while a customer came.

Print the EARLIEST hour j that achieves the smallest penalty.

YYNY -> 2 closing at hour 2 leaves only the final Y missed, a penalty of 1 NNNNN -> 0 never open at all YYYY -> 4 stay open the whole time YNNY -> 1

Closing at 0 means never opening, and closing at m means staying open throughout. Both are allowed.

## What most people try first

Evaluate every j by counting from scratch: O(m) per candidate and O(m^2) overall, which is 10^10 at m = 100000. It is the brute force this problem was checked against.

## Update the penalty as the boundary moves

Start at j = 0, where the shop never opens and the penalty is the number of Ys.

Moving the boundary from j to j + 1 opens exactly one more hour, hour j:

if hour j is 'N': penalty += 1 now open with nobody there if hour j is 'Y': penalty -= 1 that customer is no longer missed

so one pass evaluates every candidate:

cur = number of 'Y' in the whole string best = cur; bestJ = 0 for j from 0 to m-1: cur += (s[j] == 'N') ? +1 : -1 if cur < best: best = cur; bestJ = j + 1

## Why the update is exact

Each hour contributes to the penalty independently of the others: an N hour costs 1 when open and 0 when shut, a Y hour costs 0 when open and 1 when shut. So the penalty is a sum of m independent terms, and moving the boundary by one changes exactly one of them.

No greedy CHOICE is being made here. What is greedy is the refusal to recompute: the answer for j + 1 is derived from the answer for j in constant time, which is the same trade this whole block is built on.

## The strict comparison is the whole tie-break

The question asks for the EARLIEST best hour, so the update must be cur < best and never cur <= best. With <=, NYNYNY answers 4 instead of 0, because the penalty returns to its minimum several times.

## Two off-by-ones

There are m + 1 candidates, not m: closing at 0 and closing at m are both legal. And bestJ is j + 1, not j, because opening hour j corresponds to closing at j + 1.

NNNNN answers 0 and YYYY answers 4, and those two cases pin both ends.

## Overflow

The penalty is at most m = 100000. The 32 bit limit of 2147483647 is not in play.

## Cost

Time O(m). Space O(1).

Constraints - `1 ≤ m ≤ 100000` - the line contains only `Y` and `N`