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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Penalty for a Shop

Difficulty: Medium

Problem Description

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 i-th character is 'Y', it means that customers come at the i-th hour
  • whereas 'N' indicates that no customers come at the i-th hour.

If the shop closes at the j-th 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.
  • For every hour when the shop is closed and customers come, the penalty increases by 1.

Return the earliest hour at which the shop must be closed to incur a minimum penalty.

Key Insights

  • The penalty is composed of two components: open hours without customers and closed hours with customers.
  • We need to evaluate the penalty for every possible closing hour from 0 to n.
  • The aim is to find the hour with the minimum penalty, preferring the earliest hour in case of ties.

Space and Time Complexity

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

Solution

To solve this problem, we can iterate through the string customers while maintaining a running count of the penalties for both open and closed hours. We will calculate the penalty in a single pass by determining the penalty incurred by opening hours without customers and closed hours with customers. We will keep track of the minimum penalty encountered and the corresponding hour.

  1. Initialize variables for the penalty and a counter for customers.
  2. Loop through each hour:
    • Count penalties for open hours with 'N'.
    • Count penalties for closed hours with 'Y'.
  3. Update the minimum penalty and the hour if a new minimum is found.
  4. Return the hour with the minimum penalty.

Code Solutions

def bestClosingTime(customers: str) -> int:
    n = len(customers)
    min_penalty = float('inf')  # Start with an infinitely large penalty
    best_hour = 0
    current_penalty = 0

    # Calculate the penalty for closing at each hour
    for hour in range(n):
        if customers[hour] == 'N':
            current_penalty += 1  # Increment penalty for open hour with no customers

    # Now check for each closing hour
    for hour in range(n + 1):
        if hour > 0 and customers[hour - 1] == 'Y':
            current_penalty += 1  # Increment penalty for closing hour with customers
        if current_penalty < min_penalty:  # Found a new minimum penalty
            min_penalty = current_penalty
            best_hour = hour
        if hour < n and customers[hour] == 'N':
            current_penalty -= 1  # Decrement penalty for open hour without customers

    return best_hour
← Back to All Questions