Minimum Penalty for a Shop

main.md

Question

Approach

To minimize the penalty, I think of each possible closing hour j from 0 to n and compute how many wrong decisions happen: every 'N' before j adds 1 to the penalty because the shop stayed open for no reason, and every 'Y' from j onward adds 1 because the shop was closed when customers came. Instead of recomputing this every time, I track the penalty as I move j from left to right. I start with the penalty equal to the total number of 'Y' characters (meaning: if I closed at hour 0, I miss all customers). Then, for each hour i, if the character is 'Y', moving the closing time past this hour reduces the penalty by 1 (because this customer is now served). If it is 'N', the penalty increases by 1 (because now we are open during a no-customer hour). As I sweep through the string, I keep track of the minimum penalty seen and the earliest hour where it happens. The answer is that earliest hour.

Implementation

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        penalty = customers.count('Y')
        min_penalty = penalty
        best_hour = 0
        
        for i, c in enumerate(customers):
            if c == 'Y':
                penalty -= 1  
            else:
                penalty += 1   
            
            if penalty < min_penalty:
                min_penalty = penalty
                best_hour = i + 1 
        
        return best_hour

Complexities

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