Minimum Penalty for a Shop — LeetCode 2483 Python Solution

The problem

You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y': if the ith character is 'Y', it means that customers come at the ith hour whereas 'N' indicates that no customers come at the ith hour. If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as follows: For every hour when the shop is open and no customers come, the penalty increases by 1.

Example

Input

customers = "YYNY"

Output

2

Explanation

- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.

Python solution

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

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2483. Minimum Penalty for a Shop is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems