2483. Minimum Penalty for a Shop - Explanation

1. Brute Force

Intuition

The shop can close at any hour from 0 to n (inclusive). If we close at hour i, we incur a penalty of 1 for each 'N' before hour i (shop was open but no customer) and 1 for each 'Y' from hour i onward (shop was closed but customer came). We try every possible closing time and pick the one with minimum penalty.

Algorithm

Initialize res and minPenalty to n (worst case).
For each possible closing hour i from 0 to n:
- Count 'N' characters in positions 0 to i-1 (penalty for being open when no one came).
- Count 'Y' characters in positions i to n-1 (penalty for being closed when customers came).
- If this total penalty is less than minPenalty, update minPenalty and res.
Return res.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)
        res = n
        minPenalty = n

        for i in range(n + 1):
            penalty = 0
            for j in range(i):
                if customers[j] == 'N':
                    penalty += 1
            for j in range(i, n):
                if customers[j] == 'Y':
                    penalty += 1

            if penalty < minPenalty:
                minPenalty = penalty
                res = i

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Prefix & Suffix

Intuition

Instead of recounting 'N' and 'Y' characters for each closing hour, we precompute prefix counts of 'N' and suffix counts of 'Y'. The prefix array tells us how many 'N' characters appear before each position, and the suffix array tells us how many 'Y' characters appear from each position onward. The penalty at any closing hour is simply the sum of these two precomputed values.

Algorithm

Build prefixN[i] = count of 'N' in positions 0 to i-1.
Build suffixY[i] = count of 'Y' in positions i to n-1.
For each closing hour i from 0 to n:
- Calculate penalty as prefixN[i] + suffixY[i].
- Track the minimum penalty and its corresponding hour.
Return the hour with minimum penalty.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)
        cnt = 0

        prefixN = []
        for c in customers:
            prefixN.append(cnt)
            if c == 'N':
                cnt += 1
        prefixN.append(cnt)

        suffixY = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffixY[i] = suffixY[i + 1]
            if customers[i] == 'Y':
                suffixY[i] += 1

        res = n
        minPenalty = n
        for i in range(n + 1):
            penalty = prefixN[i] + suffixY[i]
            if penalty < minPenalty:
                minPenalty = penalty
                res = i

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Iteration (Two Pass)

Intuition

We can avoid storing arrays by computing on the fly. First, count all 'Y' characters. This represents the penalty if we close at hour 0 (we miss all customers). Then iterate through the string: each 'Y' we pass reduces the penalty (we served them), and each 'N' we pass increases it (we were open for nothing). Track the minimum penalty as we go.

Algorithm

Count total 'Y' characters as cntY. Initialize minPenalty = cntY, res = 0, and cntN = 0.
Iterate through each character at index i:
- If it is 'Y', decrement cntY (one fewer missed customer).
- If it is 'N', increment cntN (one more wasted open hour).
- Calculate penalty as cntN + cntY.
- If penalty is less than minPenalty, update minPenalty and set res = i + 1.
Return res.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        cntY = sum(c == "Y" for c in customers)

        minPenalty = cntY
        res = cntN = 0
        for i, c in enumerate(customers):
            if c == "Y":
                cntY -= 1
            else:
                cntN += 1

            penalty = cntN + cntY
            if penalty < minPenalty:
                res = i + 1
                minPenalty = penalty

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

4. Iteration (One Pass)

Intuition

We can solve this in a single pass using a clever observation. Instead of tracking absolute penalty, we track a relative score. Treat 'Y' as +1 (benefit of staying open) and 'N' as -1 (cost of staying open). As we iterate, we accumulate this score. The optimal closing time is right after the point where this cumulative score is maximized, meaning we captured the most value from being open.

Algorithm

Initialize res = 0, minPenalty = 0, and penalty = 0.
Iterate through each character at index i:
- Add +1 if the character is 'Y', otherwise add -1.
- If penalty > minPenalty, update minPenalty = penalty and res = i + 1.
Return res.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        res = minPenalty = 0
        penalty = 0

        for i, c in enumerate(customers):
            penalty += 1 if c == 'Y' else -1

            if penalty > minPenalty:
                minPenalty = penalty
                res = i + 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Confusing Closing Time Semantics

The shop closes at hour i means it is open during hours 0 to i-1 and closed from hour i onward. Many solutions incorrectly interpret this as the shop being open during hour i, leading to off-by-one errors in penalty calculations.

Not Considering Closing at Hour 0 or Hour n

Valid closing times range from 0 (never open) to n (open all day). Forgetting to check i = 0 or i = n causes missing the optimal answer when the best strategy is to never open or stay open the entire day.

Returning Wrong Index on Tie

When multiple closing times have the same minimum penalty, the problem asks for the earliest one. Using <= instead of < when updating the result, or not iterating in the correct order, can return a later hour instead of the earliest optimal hour.