Problem Description

You are given a string customers that represents the customer visit log of a shop. The string consists only of characters 'N' and 'Y':

• 'Y' at position i means customers come at the ith hour
• 'N' at position i means no customers come at the ith hour

The shop can choose to close at any hour j (where 0 <= j <= n, and n is the length of the string). When the shop closes at hour j, it means the shop is closed starting from hour j.

The penalty is calculated based on two scenarios:

1. When the shop is open (hours before j) but no customers come (character is 'N'), the penalty increases by 1
2. When the shop is closed (hours from j onwards) but customers come (character is 'Y'), the penalty increases by 1

Your task is to find the earliest hour at which the shop should close to minimize the total penalty.

For example, if customers = "YYNY":

• If closing at hour 0: shop is never open, penalty = 3 (missed customers at hours 0, 1, 3)
• If closing at hour 1: shop open at hour 0, penalty = 2 (missed customers at hours 1, 3)
• If closing at hour 2: shop open at hours 0-1, penalty = 1 (missed customer at hour 3)
• If closing at hour 3: shop open at hours 0-2, penalty = 1 (no customers at hour 2)
• If closing at hour 4: shop open at hours 0-3, penalty = 1 (no customers at hour 2)

The minimum penalty is 1, achieved at hours 2, 3, or 4, so return 2 (the earliest hour).

Intuition

The key insight is that for any closing time j, we can calculate the total penalty by counting two types of "mismatches":

1. Hours before j where the shop is open but no customers come ('N' characters)
2. Hours from j onwards where the shop is closed but customers come ('Y' characters)

To efficiently calculate these penalties for all possible closing times, we can use prefix sums. If we know how many 'Y' characters appear in the first i positions, we can quickly determine:

• How many 'N' characters are before position j (which equals j - count_of_Y_before_j)
• How many 'Y' characters are from position j onwards (which equals total_Y - count_of_Y_before_j)

By precomputing a prefix sum array s where s[i] represents the number of 'Y' characters in the first i positions, we can calculate the penalty for closing at hour j as:

• Penalty from being open with no customers: j - s[j]
• Penalty from being closed with customers: s[n] - s[j]
• Total penalty: j - s[j] + s[n] - s[j] = j - 2*s[j] + s[n]

Since we want the minimum penalty and the earliest hour that achieves it, we iterate through all possible closing times from 0 to n, calculate each penalty, and keep track of the minimum penalty and its corresponding earliest hour.

Learn more about Prefix Sum patterns.

Solution Approach

The solution uses prefix sum combined with enumeration to efficiently find the optimal closing time.

Step 1: Build Prefix Sum Array

First, we create a prefix sum array s of size n + 1 where s[i] stores the count of 'Y' characters in the first i positions of the string:

s = [0] * (n + 1)
for i, c in enumerate(customers):
    s[i + 1] = s[i] + int(c == 'Y')

For example, if customers = "YYNY", then s = [0, 1, 2, 2, 3].

Step 2: Enumerate All Possible Closing Times

We iterate through each possible closing hour j from 0 to n (inclusive) and calculate the penalty for each:

ans, cost = 0, inf
for j in range(n + 1):
    t = j - s[j] + s[-1] - s[j]
    if cost > t:
        ans, cost = j, t

The penalty formula t = j - s[j] + s[-1] - s[j] breaks down as:

• j - s[j]: Number of hours before j where shop is open but no customers come (count of 'N' before position j)
• s[-1] - s[j]: Number of hours from j onwards where shop is closed but customers come (count of 'Y' from position j to end)
• s[-1] is the total number of 'Y' characters in the entire string

Step 3: Track Minimum Penalty

We maintain two variables:

• cost: The minimum penalty found so far (initialized to infinity)
• ans: The earliest closing hour that achieves this minimum penalty

Whenever we find a strictly smaller penalty (cost > t), we update both the answer and the minimum cost. Since we iterate from hour 0 to n, we automatically get the earliest hour when there are ties.

Time Complexity: O(n) - We make one pass to build the prefix sum and another to find the best closing time.

Space Complexity: O(n) - For storing the prefix sum array.

Example Walkthrough

Let's walk through the solution with customers = "NYNY".

Step 1: Build the prefix sum array

We create array s where s[i] counts the number of 'Y' characters in the first i positions:

• s[0] = 0 (no characters counted yet)
• s[1] = 0 (first character is 'N', no 'Y' found)
• s[2] = 1 (second character is 'Y', total count = 1)
• s[3] = 1 (third character is 'N', count stays at 1)
• s[4] = 2 (fourth character is 'Y', total count = 2)

So s = [0, 0, 1, 1, 2]

Step 2: Calculate penalty for each closing hour

For each closing hour j, we use the formula: penalty = j - 2*s[j] + s[4]

• j = 0 (shop never opens):

  • Penalty = 0 - 2*0 + 2 = 2
  • This counts the 2 'Y' characters we miss (at positions 1 and 3)

• j = 1 (shop open at hour 0):

  • Penalty = 1 - 2*0 + 2 = 3
  • Open with no customers at hour 0 (penalty +1)
  • Closed but customers come at hours 1 and 3 (penalty +2)

• j = 2 (shop open at hours 0-1):

  • Penalty = 2 - 2*1 + 2 = 2
  • Open with no customers at hour 0 (penalty +1)
  • Closed but customers come at hour 3 (penalty +1)

• j = 3 (shop open at hours 0-2):

  • Penalty = 3 - 2*1 + 2 = 4
  • Open with no customers at hours 0 and 2 (penalty +2)
  • Closed but customers come at hour 3 (penalty +1)
  • Wait, let's recalculate: we have 'N' at position 0 and 'N' at position 2, so penalty from being open = 2. We have 'Y' at position 3, so penalty from being closed = 1. Total = 3.
  • Using formula: 3 - 2*1 + 2 = 3

• j = 4 (shop always open):

  • Penalty = 4 - 2*2 + 2 = 2
  • Open with no customers at hours 0 and 2 (penalty +2)
  • Never closed, so no penalty from closed hours

Step 3: Find the minimum

The penalties are: [2, 3, 2, 3, 2]

The minimum penalty is 2, which occurs at hours 0, 2, and 4. Since we want the earliest hour, we return 0.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main loops:

1. The first loop iterates through the customers string once to build the prefix sum array s, taking O(n) time.
2. The second loop iterates from 0 to n+1 to calculate the penalty for each possible closing time, taking O(n+1) = O(n) time.

Each operation inside both loops (array access, arithmetic operations, and comparisons) takes O(1) time. Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

• The prefix sum array s of size n+1, which requires O(n+1) = O(n) space.
• A few constant variables (ans, cost, t, i, j), which require O(1) space.

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error with Closing Hour Interpretation

A common mistake is misunderstanding what "closing at hour j" means. Many developers incorrectly assume that closing at hour j means the shop is still open during hour j and closes after it.

Incorrect Understanding:

# Wrong: Treating hour j as still open
for closing_hour in range(n + 1):
    # Incorrectly counting j as an open hour
    penalty_before = closing_hour + 1 - prefix_sum[closing_hour + 1]  # WRONG!
    penalty_after = prefix_sum[-1] - prefix_sum[closing_hour + 1]     # WRONG!

Correct Understanding:

• Closing at hour j means the shop is closed starting from hour j
• Hours 0 to j-1 are open, hours j to n-1 are closed
• This is why we use prefix_sum[closing_hour] not prefix_sum[closing_hour + 1]

2. Forgetting the Edge Case of Never Opening or Never Closing

Some implementations forget that the shop can close at hour 0 (never open) or hour n (never close).

Incomplete Range:

# Wrong: Missing edge cases
for closing_hour in range(1, n):  # Misses hour 0 and hour n!
    # Calculate penalty...

Complete Solution:

# Correct: Include all possibilities from 0 to n
for closing_hour in range(n + 1):  # Includes 0 (never open) and n (always open)
    # Calculate penalty...

3. Using Wrong Comparison for Finding Minimum

When multiple hours have the same minimum penalty, we need the earliest one. Using >= instead of > would give us the latest hour with minimum penalty.

Wrong Comparison:

# Wrong: This would give the LATEST hour with minimum penalty
for closing_hour in range(n + 1):
    total_penalty = calculate_penalty(closing_hour)
    if total_penalty <= min_penalty:  # WRONG! Uses <=
        best_hour = closing_hour
        min_penalty = total_penalty

Correct Comparison:

# Correct: This gives the EARLIEST hour with minimum penalty
for closing_hour in range(n + 1):
    total_penalty = calculate_penalty(closing_hour)
    if total_penalty < min_penalty:  # Correct! Uses strict <
        best_hour = closing_hour
        min_penalty = total_penalty

4. Inefficient Penalty Calculation

Without using prefix sums, recalculating the penalty for each closing hour becomes O(n²) instead of O(n).

Inefficient Approach:

# Wrong: O(n²) time complexity
for closing_hour in range(n + 1):
    penalty = 0
    # Count 'N's before closing
    for i in range(closing_hour):
        if customers[i] == 'N':
            penalty += 1
    # Count 'Y's after closing
    for i in range(closing_hour, n):
        if customers[i] == 'Y':
            penalty += 1

Efficient Solution with Prefix Sum:

# Correct: O(n) time complexity using prefix sum
prefix_sum = [0] * (n + 1)
for i, c in enumerate(customers):
    prefix_sum[i + 1] = prefix_sum[i] + (1 if c == 'Y' else 0)

for closing_hour in range(n + 1):
    penalty = (closing_hour - prefix_sum[closing_hour]) + (prefix_sum[-1] - prefix_sum[closing_hour])