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)
1#include <stdio.h>
2#include <string.h>
3
4int minimumPenalty(char* customers) {
5 int n = strlen(customers);
6 int penalty = 0, min_penalty = n, min_hour = 0;
7 int y_prefix[n+1];
8 int n_suffix[n+1];
9
10 y_prefix[0] = 0;
11 for (int i = 0; i < n; i++) {
12 y_prefix[i+1] = y_prefix[i] + (customers[i] == 'Y');
13 }
14
15 n_suffix[n] = 0;
16 for (int i = n - 1; i >= 0; i--) {
17 n_suffix[i] = n_suffix[i+1] + (customers[i] == 'N');
18 }
19
20 for (int j = 0; j <= n; j++) {
21 penalty = y_prefix[j] + n_suffix[j];
22 if (penalty < min_penalty) {
23 min_penalty = penalty;
24 min_hour = j;
25 }
26 }
27
28 return min_hour;
29}
30
31int main() {
32 char customers[] = "YYNY";
33 int result = minimumPenalty(customers);
34 printf("%d\n", result);
35 return 0;
36}The implementation uses prefix and suffix arrays to keep track of Y and N counts up to each hour. This preprocessing helps calculate the penalty efficiently for each potential closing time point.
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.