We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Penalty for a Shop

Number: 2576

Difficulty: Medium

Paid? No

Companies: Google, Stripe, Amazon

Problem Description

Given a string customers where each character is either 'Y' (a customer arrives) or 'N' (no customer), determine the earliest hour (0 <= j <= n, where n is the length of customers) at which closing the shop minimizes the total penalty. The penalty is computed as follows:

  • For every hour the shop is open (i.e., hours before the closing time) with no customer ('N'), incur a penalty of 1.
  • For every hour the shop is closed (i.e., hours from the closing time onward) when a customer would have arrived ('Y'), incur a penalty of 1.

Return the earliest hour at which the shop should close to achieve the minimum penalty.

Key Insights

  • Use a prefix-sum-like technique to efficiently compute the penalty for any closing time.
  • The cost of closing at a particular hour j is the sum of:
    • The number of 'N's in the open hours (first j hours).
    • The number of 'Y's in the closed hours (from hour j to the end).
  • By iterating through the string and updating counts dynamically, we can calculate the penalty in O(n) time.
  • Maintain and update two counters (open penalty and remaining suffix penalty) as you traverse the string.

Space and Time Complexity

Time Complexity: O(n) – we traverse the string once. Space Complexity: O(1) – only a few integer variables are used.

Solution

We approach the problem by first counting the total number of 'Y's which represents the penalty if the shop were closed at hour 0 (all potential visits are missed). We then iterate over each hour and:

  • If the hour is 'N', increment the open penalty since it’s an hour open with no visitor.
  • If the hour is 'Y', decrement the suffix penalty since that hour would now be open and thus not incur a penalty. At every step, the total penalty is the sum of the open penalty and the current suffix penalty. We keep track of the minimal penalty and the first hour that achieves it.

Code Solutions

# Python solution with line-by-line comments.

def bestClosingTime(customers: str) -> int:
    n = len(customers)
    # Total number of 'Y' in the string, representing penalty if closed at hour 0.
    total_customers = customers.count('Y')
    min_penalty = total_customers  # Penalty if shop closed at 0-th hour.
    best_hour = 0
    open_penalty = 0  # Accumulates penalty from open hours with no customers.
    current_suffix = total_customers  # Penalty from closed hours with missed visitors.
    
    # Iterate over each hour; consider index hour as an open hour.
    for hour in range(n):
        # If no customer comes during this hour, increment open penalty.
        if customers[hour] == 'N':
            open_penalty += 1
        else:
            # If a customer would have arrived, decrease the suffix penalty.
            current_suffix -= 1
        
        # Total penalty after making hour (hour) open (thus closing at hour+1).
        penalty = open_penalty + current_suffix
        if penalty < min_penalty:
            min_penalty = penalty
            best_hour = hour + 1  # Shop closes immediately after hour.
            
    return best_hour

# Example usage:
print(bestClosingTime("YYNY"))  # Expected output: 2
← Back to All Questions