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)
1public class Main {
2 public static int minimumPenalty(String customers) {
3 int n = customers.length();
4 int[] y_prefix = new int[n + 1];
5 int[] n_suffix = new int[n + 1];
6
7 for (int i = 0; i < n; ++i) {
8 y_prefix[i + 1] = y_prefix[i] + (customers.charAt(i) == 'Y' ? 1 : 0);
9 }
10
11 for (int i = n - 1; i >= 0; --i) {
12 n_suffix[i] = n_suffix[i + 1] + (customers.charAt(i) == 'N' ? 1 : 0);
13 }
14
15 int min_penalty = n, min_hour = 0;
16 for (int j = 0; j <= n; ++j) {
17 int penalty = y_prefix[j] + n_suffix[j];
18 if (penalty < min_penalty) {
19 min_penalty = penalty;
20 min_hour = j;
21 }
22 }
23
24 return min_hour;
25 }
26
27 public static void main(String[] args) {
28 String customers = "YYNY";
29 int result = minimumPenalty(customers);
30 System.out.println(result);
31 }
32}The solution creates arrays to store cumulative counts of 'Y' up to each hour and 'N' from each hour to the end, which are used to quickly compute penalties for closing at each hour.
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.