leetcode

commit 1fa352f782e5c1352e7824a927238e06eddd2604
parent 9839f33accf1187e951dcfc0a86f37e52296c04e
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri,  6 Mar 2026 20:50:39 -0700

1888. minimum number of flips to make the binary string alternating

Diffstat:
M
min_flips_bin_string.c
 | 
54
+++++++++++++++++++++---------------------------------
M
min_flips_bin_string.py
 | 
38
++++++++++----------------------------

2 files changed, 31 insertions(+), 61 deletions(-)
diff --git a/min_flips_bin_string.c b/min_flips_bin_string.c
@@ -1,9 +1,5 @@
 // 1888. Minimum Number of Flips to Make the Binary String Alternating
-#include <limits.h>
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
 
 /*
  * you are given a binary string 's'. you are allowed to perform two types of
@@ -17,37 +13,29 @@
  */
 
 int minFlips(char *s) {
-  int n = strlen(s), idx = 0, min_ops = INT_MAX, diff1 = 0, diff2 = 0, left = 0,
-      right = 0;
-  char *g_str = calloc(1, 2 * n + 1);
-  char *z_tar = calloc(1, 2 * n + 1);
-  char *o_tar = calloc(1, 2 * n + 1);
-  strcat(g_str, s);
-  strcat(g_str, s);
-  for (int i = 0; i < 2 * n; i++) {
-    z_tar[idx] = i % 2 ? '1' : '0';
-    o_tar[idx++] = i % 2 ? '0' : '1';
-  }
-  while (right < 2 * n) {
-    diff1 += g_str[right] != z_tar[right];
-    diff2 += g_str[right] != o_tar[right];
-    if (right - left + 1 > n) {
-      if (g_str[left] != z_tar[left])
-        diff1--;
-      if (g_str[left] != o_tar[left])
-        diff2--;
-      left++;
+  int n = 0, k = 0;
+  for (char c = *s; c; c = s[++n])
+    k += (n ^ c) & 1;
+  int m = fmin(k, n - k);
+  if (n & 1) {
+    int i = 0;
+    for (char c = *s; c; c = s[++i]) {
+      k += ((i ^ c ^ 1) & 1) - ((i ^ c) & 1);
+      m = fmin(m, fmin(k, n - k));
     }
-    if (right - left + 1 == n)
-      min_ops = fmin(min_ops, fmin(diff1, diff2));
-    right++;
   }
-  return min_ops;
+  return m;
 }
 
 int main() {
-  char s1[] = {"111000"}, s2[] = {"010"}, s3[] = {"1110"};
-  printf("%d\n", minFlips(s1)); // expect: 2
-  printf("%d\n", minFlips(s2)); // expect: 0
-  printf("%d\n", minFlips(s3)); // expect: 1
+  char *s1 = "111000", *s2 = "010", *s3 = "1110";
+  int r1 = minFlips(s1);
+  int r2 = minFlips(s2);
+  int r3 = minFlips(s3);
+  printf("%d\n", r1); // expect: 2
+  assert(r1 == 2);
+  printf("%d\n", r2); // expect: 0
+  assert(r2 == 0);
+  printf("%d\n", r3); // expect: 1
+  assert(r3 == 1);
 }
diff --git a/min_flips_bin_string.py b/min_flips_bin_string.py
@@ -12,35 +12,17 @@ alternating, while the string "0110" is not.
 """
 
 
-class Solution(object):
-    def minFlips(self, s):
+class Solution:
+    def minFlips(self, s: str) -> int:
         n = len(s)
-        k = len(s)
-        s = s if k % 2 == 0 else s + s
-        arr1, arr2 = [], []
-        for i in range(n):
-            arr1.append("0" if i % 2 == 0 else "1")
-            arr2.append("1" if i % 2 == 0 else "0")
-        alt1 = "".join(arr1)
-        alt2 = "".join(arr2)
-        diff1, diff2 = 0, 0
-        i, j = 0, 0
-        while j < n:
-            if s[j] != alt1[j]:
-                diff1 += 1
-            if s[j] != alt2[j]:
-                diff2 += 1
-            if j - i + 1 < k:
-                j += 1
-            else:
-                n = min(n, diff1, diff2)
-                if s[i] != alt1[i]:
-                    diff1 -= 1
-                if s[i] != alt2[i]:
-                    diff2 -= 1
-                i += 1
-                j += 1
-        return n
+        e, o = (n + 1) // 2, n // 2
+        x = s[::2].count("1") - s[1::2].count("1")
+        m = min(e - x, o + x)
+        if n & 1:
+            for c in s:
+                x = 2 * (ord(c) & 1) - x
+                m = min(m, e - x, o + x)
+        return m
 
 
 if __name__ == "__main__":