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.
By employing two counters for 'N' without customers and 'Y' with customers, this approach reduces overhead and efficiently updates penalties as hours switch state.