#2483

Medium

LeetCode Problem Workspace

Minimum Penalty for a Shop

Determine the earliest closing hour of a shop to minimize penalty using a string of customer visits and prefix sums.

Problem Statement

You are given a string customers representing hourly customer visits in a shop, where 'Y' indicates a visit and 'N' indicates no visit. The shop may close at any hour from 0 to n.

If the shop closes at hour j, the penalty is the sum of 'N's before hour j and 'Y's after hour j. Return the earliest hour to close the shop to achieve the minimum total penalty.

Examples

Example 1

Input: customers = "YYNY"

Output: 2

Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty. Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.

Example 2

Input: customers = "NNNNN"

Output: 0

It is best to close the shop at the 0th hour as no customers arrive.

Example 3

Input: customers = "YYYY"

Output: 4

It is best to close the shop at the 4th hour as customers arrive at each hour.

Constraints

1 <= customers.length <= 105
customers consists only of characters 'Y' and 'N'.

Solution Approach

Prefix and Suffix Counts

Compute a prefix sum array for 'N' counts and maintain a running suffix count for 'Y'. This captures penalties before and after each potential closing hour efficiently.

Iterate Over Closing Hours

Loop through all hours from 0 to n, calculate total penalty at each hour using prefix and suffix counts, and track the minimum penalty and earliest corresponding hour.

Return Earliest Minimum

After scanning all hours, return the smallest hour that achieved the minimum penalty. This ensures the earliest optimal closing time is selected.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each character is processed once for prefix and suffix counts. Space complexity is O(1) if using running counts instead of full prefix arrays.

What Interviewers Usually Probe

Expect O(n) solution using prefix sums rather than nested loops.
Watch for off-by-one errors in computing suffix counts of 'Y'.
Early return for cases where all customers are 'N' or 'Y' may be discussed.

Common Pitfalls or Variants

Common pitfalls

Confusing prefix sum of 'N' with suffix sum of 'Y', leading to incorrect penalties.
Forgetting to include the case when the shop closes at the last hour.
Incorrectly returning the last minimum instead of the earliest minimum hour.

Follow-up variants

Calculate maximum penalty hour instead of minimum for analytical contrast.
Handle multiple shops' customer strings simultaneously with the same approach.
Allow dynamic updates to customer string and recalculate optimal closing hour efficiently.

FAQ

What does 'Minimum Penalty for a Shop' require?

It requires finding the earliest hour to close a shop to minimize penalty using a string plus prefix sum method.

How does the prefix sum approach help here?

Prefix sums of 'N' allow fast calculation of penalties before a closing hour, while suffix counts of 'Y' handle penalties after.

Can this solution handle large inputs efficiently?

Yes, the algorithm runs in O(n) time and O(1) space with running counts, suitable for up to 105 customers.

Why return the earliest hour for minimum penalty?

When multiple hours yield the same penalty, the problem specifies returning the earliest one, avoiding later hour tie-breaking issues.

Are there common mistakes to avoid?

Yes, confusing prefix and suffix counts, missing the final hour, or returning the last minimum instead of earliest are typical errors.

terminal

Solution

Solution 1: Enumeration

If the shop closes at hour $0$, then the cost is the number of character `'Y'` in $\textit{customers}$. We initialize the answer variable $\textit{ans}$ to $0$, and the cost variable $\textit{cost}$ to the number of character `'Y'` in $\textit{customers}$.

1

2

3

4

5

6

7

8

9

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        ans = 0
        mn = cost = customers.count("Y")
        for j, c in enumerate(customers, 1):
            cost += 1 if c == "N" else -1
            if cost < mn:
                ans, mn = j, cost
        return ans

Continue Practicing

#2559 count vowel strings in ranges #2391 minimum amount of time to collect garbage #2381 shifting letters ii