LeetCode 2483 - Minimum Penalty for a Shop

The problem asks us to determine the optimal hour to close a shop to minimize a penalty based on customer arrivals. The input is a string customers where each character represents an hour: 'Y' means customers arrive, and 'N' means no customers arrive.

leetcodemediumstringprefix-sum

LeetCode Problem 2483

Difficulty: 🟡 Medium
Topics: String, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine the optimal hour to close a shop to minimize a penalty based on customer arrivals. The input is a string customers where each character represents an hour: 'Y' means customers arrive, and 'N' means no customers arrive. The shop can close at any hour from 0 to n (inclusive), and the penalty is calculated as follows: every hour the shop is open with no customers incurs a penalty of 1, and every hour the shop is closed with customers arriving also incurs a penalty of 1.

The expected output is the earliest hour at which the shop should close to incur the minimum penalty. This problem is constrained by the fact that the input string can be as long as 10^5, meaning any brute-force approach that recalculates the penalty for every possible closing hour will be too slow. Important edge cases include when all hours have customers ("YYYY"), no hours have customers ("NNNN"), or when multiple hours yield the same minimal penalty, in which case the earliest hour must be returned.

Approaches

The brute-force approach calculates the penalty for every possible closing hour. For each hour j, we iterate through the first j hours to count open-but-empty penalties and iterate through the remaining hours to count closed-but-busy penalties. This gives the correct answer but is inefficient, with a time complexity of O(n²), which is infeasible for n = 10^5.

The optimal approach leverages a prefix sum style calculation. Instead of recalculating penalties for each closing hour, we maintain a running penalty score by iterating once through the string. We start with a hypothetical shop closing at hour 0, which would incur a penalty equal to the number of 'Y' in the string. As we iterate, we adjust the penalty: opening an hour with 'N' increases the penalty by 1, while opening an hour with 'Y' decreases the penalty by 1 because it moves from closed to open. We track the minimum penalty and its earliest index during this iteration. This reduces the time complexity to O(n) and space complexity to O(1).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compute penalty for each possible closing hour by iterating over all hours repeatedly
Optimal O(n) O(1) Single pass with a running penalty count using a prefix sum-style update

Algorithm Walkthrough

  1. Initialize penalty to the total number of 'Y' in customers. This represents the penalty if the shop closes at hour 0, as all hours with customers would incur a penalty.
  2. Set min_penalty to this initial penalty and best_hour to 0.
  3. Iterate over the string with an index i from 0 to n-1.
  4. For each hour:
  • If customers[i] is 'Y', decrement penalty by 1. This accounts for moving this hour from closed to open, reducing penalty.
  • If customers[i] is 'N', increment penalty by 1. This accounts for being open but empty, increasing penalty.
  1. After adjusting, if penalty is less than min_penalty, update min_penalty and set best_hour to i + 1.
  2. Continue until the end of the string. Return best_hour.

Why it works: At each step, the penalty variable correctly represents the penalty if the shop closes immediately after the current hour. By tracking the minimum value and its first occurrence, we ensure that the earliest hour with minimum penalty is returned.

Python Solution

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:  # c == 'N'
                penalty += 1
            
            if penalty < min_penalty:
                min_penalty = penalty
                best_hour = i + 1
        
        return best_hour

The code starts by assuming the shop closes at hour 0 and counts all 'Y' as penalties. As we iterate through each hour, the penalty is adjusted according to the current hour's customer status. If a new minimum penalty is found, the best_hour is updated to the hour after the current one because the shop closes after this hour.

Go Solution

func bestClosingTime(customers string) int {
    penalty := 0
    for _, c := range customers {
        if c == 'Y' {
            penalty++
        }
    }
    
    minPenalty := penalty
    bestHour := 0
    
    for i, c := range customers {
        if c == 'Y' {
            penalty--
        } else { // c == 'N'
            penalty++
        }
        
        if penalty < minPenalty {
            minPenalty = penalty
            bestHour = i + 1
        }
    }
    
    return bestHour
}

The Go version mirrors the Python solution. The main difference is using range to iterate over the string and explicitly handling rune comparison. The logic for updating the penalty and tracking the minimum remains identical.

Worked Examples

Example 1: customers = "YYNY"

Hour i customers[i] Penalty before Penalty after Min Penalty Best Hour
0 'Y' 3 2 2 1
1 'Y' 2 1 1 2
2 'N' 1 2 1 2
3 'Y' 2 1 1 2

Optimal hour: 2

Example 2: customers = "NNNNN"

Penalty starts at 0. Each 'N' increases penalty. Minimum occurs at hour 0. Optimal hour: 0

Example 3: customers = "YYYY"

Penalty starts at 4. Each 'Y' decreases penalty. Minimum occurs at hour 4. Optimal hour: 4

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the string once to initialize and once to compute the running penalty.
Space O(1) Only a few integer variables are used; no additional data structures scale with n.

The single-pass approach ensures linear time regardless of string length, which is efficient for up to 10^5 characters.

Test Cases

# Provided examples
assert Solution().bestClosingTime("YYNY") == 2  # multiple minimums, earliest chosen
assert Solution().bestClosingTime("NNNNN") == 0  # no customers at all
assert Solution().bestClosingTime("YYYY") == 4  # customers all hours

# Edge cases
assert Solution().bestClosingTime("Y") == 1  # single customer
assert Solution().bestClosingTime("N") == 0  # single hour empty
assert Solution().bestClosingTime("NYNYNYNY") == 4  # alternating pattern

# Stress case
assert Solution().bestClosingTime("N" * 50000 + "Y" * 50000) == 50000  # large input
Test Why
"YYNY" Tests multiple minimum penalties, ensuring earliest hour is chosen
"NNNNN" Tests all hours empty
"YYYY" Tests all hours with customers
"Y" / "N" Single-character edge cases
"NYNYNYNY" Alternating pattern
Large input Ensures algorithm handles maximum constraints

Edge Cases

All customers arrive ('YYYY'): The optimal strategy is to remain open all hours. Our code correctly counts the penalty decrement for each 'Y' and returns n.

All hours are empty ('NNNN'): The optimal strategy is to close immediately. Our code starts with zero penalty and increments for each 'N' correctly, resulting in hour 0.

Multiple optimal hours: When more than one closing hour yields the same minimum penalty, the algorithm must choose the earliest. By updating best_hour only when a new minimum is strictly found, we naturally preserve the earliest index.

These cases cover the main potential pitfalls and demonstrate the correctness of the single-pass approach.