Minimum Penalty for a Shop

How it works

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.

Steps

1. Initialize res = 0, minPenalty = 0, and penalty = 0.
2. 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.
3. Return res.

Complexity

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

Things to watch for

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.

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

class Solution {
public:
    int bestClosingTime(string customers) {
        int res = 0, minPenalty = 0, penalty = 0;

        for (int i = 0; i < customers.size(); i++) {
            penalty += customers[i] == 'Y' ? 1 : -1;

            if (penalty > minPenalty) {
                minPenalty = penalty;
                res = i + 1;
            }
        }

        return res;
    }
};