Watch 10 video solutions for Minimum Penalty for a Shop, a medium level problem involving String, Prefix Sum. This walkthrough by NeetCodeIO has 12,499 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y':
ith character is 'Y', it means that customers come at the ith hour'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:
1.1.Return the earliest hour at which the shop must be closed to incur a minimum penalty.
Note that if a shop closes at the jth hour, it means the shop is closed at the hour j.
Example 1:
Input: customers = "YYNY" Output: 2 Explanation: - 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 Explanation: It is best to close the shop at the 0th hour as no customers arrive.
Example 3:
Input: customers = "YYYY" Output: 4 Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.
Constraints:
1 <= customers.length <= 105customers consists only of characters 'Y' and 'N'.Problem Overview: You receive a customers string where 'Y' means a customer arrives that hour and 'N' means no one comes. If the shop stays open during an 'N', you incur a penalty. If the shop is closed during a 'Y', you also incur a penalty. The task is to choose the closing hour that produces the minimum total penalty.
Approach 1: Brute Force Simulation (O(n²) time, O(1) space)
Check every possible closing hour from 0 to n. For each candidate closing time, iterate through the string and compute the penalty: count 'N' while the shop is open and 'Y' while it is closed. This approach directly follows the problem definition but repeatedly scans the string for every hour. The nested iteration results in quadratic time, which becomes inefficient for large inputs.
Approach 2: Cumulative Sum / Prefix Penalty (O(n) time, O(n) space)
Precompute penalties using the idea of prefix sum. Build a prefix array that counts how many 'N' occur while the shop is open up to hour i. Build another suffix-like count for how many 'Y' occur after the closing hour. The penalty for closing at hour i becomes prefixN[i] + suffixY[i]. Iterate once to compute these values and track the minimum penalty and its earliest index. This converts repeated counting into constant-time lookups.
Approach 3: Sliding Window Penalty Tracking (O(n) time, O(1) space)
You can avoid extra arrays by updating the penalty dynamically while scanning the string. Start with the assumption that the shop closes at hour 0, meaning every 'Y' causes a penalty. While iterating from left to right, update the penalty: encountering 'Y' decreases penalty (the shop staying open avoids that penalty), while encountering 'N' increases penalty (open with no customers). Track the minimum penalty seen so far and the corresponding hour. This effectively behaves like a running prefix difference and is the most space‑efficient solution.
Recommended for interviews: The sliding window or cumulative prefix method is what interviewers typically expect. The brute force version demonstrates that you understand the penalty definition, but the optimized O(n) approach shows you recognize the prefix sum pattern and can convert repeated counting into incremental updates.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | Good for understanding the penalty definition or verifying logic on small inputs |
| Cumulative Sum / Prefix Penalty | O(n) | O(n) | When you want clear prefix-based reasoning using precomputed counts |
| Sliding Window Penalty Tracking | O(n) | O(1) | Optimal solution for interviews and production due to constant space |