Show problems as
Classic problem #2483MediumStringPrefix Sum

Minimum Penalty for a Shop

Real-world version: Choosing When to Shut the Stall
Tracked in this browser only
Read Minimum Penalty for a Shop on LeetCode(opens in a new tab)

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

A stall keeps a log log of its hours, one character per hour: Y when a customer came in that hour and N when nobody did.

The stall may shut at the start of any hour from 0 up to the number of logged hours. Shutting at hour j means the stall was open for hours 0 through j - 1 and closed for the rest.

The cost of shutting at hour j is the number of open hours with no customer plus the number of closed hours with a customer.

Return the earliest hour whose cost is the smallest.

Examples

Example 1

Input
log = "YYNN"
Output
2

Shutting at hour 2 leaves the two customer hours open and the two empty hours closed, so nothing is charged at all.

Example 2

Input
log = "NNYY"
Output
0

Never opening costs two, one for each later customer hour, and nothing beats that, so the earliest such hour is reported.

Example 3

Input
log = "Y"
Output
1

Staying open for the single customer hour costs nothing.

Constraints

  • 1 <= log.length <= 10^5
  • every character of log is Y or N

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 best_closing_time(log: str) -> int:
Java
public int bestClosingTime(String log)

More on the same topics