Brute Force Solution

The brute force solution iterates through all possible closing hours and calculates the penalty for each hour. It then returns the hour with the minimum penalty. This involves nested loops, leading to a higher time complexity.

Algorithm

1. Initialize min_penalty to infinity and earliest_hour to 0.
2. Iterate through all possible closing hours j from 0 to n (inclusive), where n is the length of the customers string.
3. For each closing hour j, calculate the penalty:
   • Iterate from 0 to j-1: If customers[i] is 'N', increment the penalty (shop is open, no customer).
   • Iterate from j to n-1: If customers[i] is 'Y', increment the penalty (shop is closed, customer arrives).
4. If the calculated penalty is less than min_penalty, update min_penalty and earliest_hour.
5. Return earliest_hour.

Code

def earliest_closing_brute_force(customers):
    n = len(customers)
    min_penalty = float('inf')
    earliest_hour = 0

    for j in range(n + 1):
        penalty = 0
        for i in range(j):
            if customers[i] == 'N':
                penalty += 1
        for i in range(j, n):
            if customers[i] == 'Y':
                penalty += 1

        if penalty < min_penalty:
            min_penalty = penalty
            earliest_hour = j

    return earliest_hour

Time and Space Complexity

• Time Complexity: O(n^2), due to the nested loops.
• Space Complexity: O(1), as we only use a few variables.

Optimal Solution

The optimal solution utilizes a prefix sum approach to calculate the penalty in O(n) time. We can precompute the number of 'Y's and 'N's to avoid redundant calculations within the loop.

Algorithm

1. Initialize min_penalty to infinity and earliest_hour to 0.
2. Calculate the initial penalty when the shop is closed at hour 0. This is equivalent to the number of 'Y's in the customers string.
3. Iterate through the customers string:
   • If customers[i] is 'Y', decrement the current penalty (because if we close the shop after this hour, we will not count this customer in the penalty).
   • If customers[i] is 'N', increment the current penalty (because if we close the shop after this hour, we add penalty).
   • If the current penalty is less than min_penalty, update min_penalty and earliest_hour to i + 1.
4. Return earliest_hour.

Code

def earliest_closing(customers):
    n = len(customers)
    min_penalty = float('inf')
    earliest_hour = 0
    penalty = 0
    for c in customers:
        if c == 'Y':
            penalty += 1

    min_penalty = penalty

    for i in range(n):
        if customers[i] == 'Y':
            penalty -= 1
        else:
            penalty += 1

        if penalty < min_penalty:
            min_penalty = penalty
            earliest_hour = i + 1

    return earliest_hour

Time and Space Complexity

• Time Complexity: O(n), as we iterate through the string once.
• Space Complexity: O(1), as we only use a few variables.

Edge Cases

• Empty string: The problem statement says that the string has at least length one so we don't need to handle empty string.
• String with only 'Y's: The optimal closing time is the last hour (n).
• String with only 'N's: The optimal closing time is the first hour (0).