Sponsored
Sponsored
This approach involves preprocessing the input string to obtain counts of 'Y' before each hour and 'N' from each hour to the end. This allows us to quickly calculate the penalty for closing the shop at any given hour.
Time Complexity: O(n)
Space Complexity: O(n)
1def minimum_penalty(customers):
2 n = len(customers)
3 y_prefix = [0] * (n + 1)
4 n_suffix = [0] * (n + 1)
5
6 for i in range(n):
7 y_prefix[i + 1] = y_prefix[i] + (1 if customers[i] == 'Y' else 0)
8
9 for i in range(n - 1, -1, -1):
10 n_suffix[i] = n_suffix[i + 1] + (1 if customers[i] == 'N' else 0)
11
12 min_penalty = n
13 min_hour = 0
14 for j in range(n + 1):
15 penalty = y_prefix[j] + n_suffix[j]
16 if penalty < min_penalty:
17 min_penalty = penalty
18 min_hour = j
19
20 return min_hour
21
22# Example usage:
23customers = "YYNY"
24result = minimum_penalty(customers)
25print(result) # Output: 2By using prefix and suffix sums, you can determine the cumulative count of 'Y' and 'N' in linear time, which allows efficient penalty calculation when considering different closing hours.
This implementation uses two counters: 'open_no_customers' for open hours without customers and 'closed_with_customers' for closed hours with customers. As we evaluate each closing hour, penalties are adjusted efficiently without needing full array storage.