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)
1function minimumPenalty(customers) {
2 const n = customers.length;
3 const yPrefix = new Array(n + 1).fill(0);
4 const nSuffix = new Array(n + 1).fill(0);
5
6 for (let i = 0; i < n; i++) {
7 yPrefix[i + 1] = yPrefix[i] + (customers[i] === 'Y' ? 1 : 0);
8 }
9
10 for (let i = n - 1; i >= 0; i--) {
11 nSuffix[i] = nSuffix[i + 1] + (customers[i] === 'N' ? 1 : 0);
12 }
13
14 let minPenalty = n;
15 let minHour = 0;
16 for (let j = 0; j <= n; j++) {
17 const penalty = yPrefix[j] + nSuffix[j];
18 if (penalty < minPenalty) {
19 minPenalty = penalty;
20 minHour = j;
21 }
22 }
23
24 return minHour;
25}
26
27// Example usage
28const customers = "YYNY";
29console.log(minimumPenalty(customers)); // Output: 2Cumulative prefix and suffix count arrays are used to capture 'Y' and 'N' counts, allowing efficient penalty computation while iterating over potential 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.