leetcode

commit 6da48e38372d7c75cbf19c14abfe103fcb7783d1
parent 1e1914035e7b964a048d492c9c818fa1f5079af6
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 25 Dec 2025 21:39:47 -0700

2483. minimum penalty for a shop

Diffstat:
M
min_penalty_shop.c
 | 
44
+++++++++++++-------------------------------
A
min_penalty_shop.py
 | 
50
++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 63 insertions(+), 31 deletions(-)
diff --git a/min_penalty_shop.c b/min_penalty_shop.c
@@ -1,8 +1,5 @@
 // 2483. Minimum Penalty for a Shop
-#include <limits.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
 
 /*
  You are given the customer visit log of a shop represented by a 0-indexed
@@ -26,37 +23,22 @@ hour j.
 */
 
 int bestClosingTime(char *customers) {
-  int n = strlen(customers);
-  int *pre_n = malloc((n + 1) * sizeof(int));
-  int *suf_y = malloc((n + 1) * sizeof(int));
-  pre_n[0] = 0;
-  for (int i = 0; i < n; i++) {
-    pre_n[i + 1] = pre_n[i];
-    if (customers[i] == 'N')
-      pre_n[i + 1]++;
+  int penalty = 0, best_penalty = 0, ans = 0;
+  for (int i = 0; customers[i] != '\0'; i++) {
+    if (customers[i] == 'Y') {
+      penalty--;
+      if (penalty < best_penalty) {
+        best_penalty = penalty;
+        ans = i + 1;
+      }
+    } else
+      penalty++;
   }
-  suf_y[n] = 0;
-  for (int i = n - 1; i >= 0; i--) {
-    suf_y[i] = suf_y[i + 1];
-    if (customers[i] == 'Y')
-      suf_y[i]++;
-  }
-  int min = INT_MAX, min_id = 0;
-  for (int i = 0; i <= n; i++) {
-    int d = pre_n[i] + suf_y[i];
-    if (d < min) {
-      min = d;
-      min_id = i;
-    }
-    if (!min)
-      break;
-  }
-  free(pre_n), free(suf_y);
-  return min_id;
+  return ans;
 }
 
 int main() {
-  char c1[] = {"YYNY"}, c2[] = {"NNNNN"}, c3[] = {"YYYY"};
+  char *c1 = "YYNY", *c2 = "NNNNN", *c3 = "YYYY";
   printf("%d\n", bestClosingTime(c1)); // expect: 2
   printf("%d\n", bestClosingTime(c2)); // expect: 0
   printf("%d\n", bestClosingTime(c3)); // expect: 4
diff --git a/min_penalty_shop.py b/min_penalty_shop.py
@@ -0,0 +1,50 @@
+# 2483. Minimum Penalty for a Shop
+
+"""
+You are given the customer visit log of a shop represented by a 0-indexed
+string customers consisting only of characters 'N' and 'Y':
+
+if the ith character is 'Y', it means that customers come at the ith hour
+whereas 'N' indicates that no customers come at the ith hour.
+
+If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as
+follows:
+
+For every hour when the shop is open and no customers come, the penalty
+increases by 1. For every hour when the shop is closed and customers come, the
+penalty increases by 1.
+
+Return the earliest hour at which the shop must be closed to incur a minimum
+penalty.
+
+Note that if a shop closes at the jth hour, it means the shop is closed at the
+hour j.
+"""
+
+
+class Solution(object):
+    def bestClosingTime(self, customers):
+        """
+        :type customers: str
+        :rtype: int
+        """
+        n, a, b = len(customers), 0, 0
+        prefix_a, prefix_b = [0], [0]
+        for i in customers:
+            a += i == "N"
+            prefix_a.append(a)
+        for i in reversed(customers):
+            b += i == "Y"
+            prefix_b.append(b)
+        prefix_b.reverse()
+        best_hour, _ = min(
+            enumerate(i + j for i, j in zip(prefix_a, prefix_b)), key=lambda x: x[1]
+        )
+        return best_hour
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.bestClosingTime(customers="YYNY"))
+    print(obj.bestClosingTime(customers="NNNNN"))
+    print(obj.bestClosingTime(customers="YYYY"))