leetcode

commit cdf8e1a0e52b86fc55f104062637e45751f36a96
parent f6409fced6cbd96171cfd8fab742d75388cce0b5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 14 Nov 2025 22:22:50 -0700

3234. count the number of substrings with dominant ones

Diffstat:
A
count_num_substrings_dominant_one.c
 | 
38
++++++++++++++++++++++++++++++++++++++
A
count_num_substrings_dominant_one.py
 | 
37
+++++++++++++++++++++++++++++++++++++

2 files changed, 75 insertions(+), 0 deletions(-)
diff --git a/count_num_substrings_dominant_one.c b/count_num_substrings_dominant_one.c
@@ -0,0 +1,38 @@
+// 3234. Count the Number of Substrings With Dominant Ones
+#include "leetcode.h"
+
+/*
+ * you are given a binary string 's'. return the number of substrings with
+ * dominant ones. a string has dominant ones if the number of ones in the string
+ * is greater than or equal to the sqaure of the number of zeroes in the string.
+ */
+
+int numberOfSubstrings(char *s) {
+  int n = strlen(s), ans = 0;
+  int *pre = (int *)malloc((n + 1) * sizeof(int));
+  pre[0] = -1;
+  for (int i = 0; i < n; i++)
+    pre[i + 1] = !i || (i > 0 && s[i - 1] == '0') ? i : pre[i];
+  for (int i = 1; i <= n; i++) {
+    int cnt0 = s[i - 1] == '0' ? 1 : 0, j = i;
+    while (j > 0 && cnt0 * cnt0 <= n) {
+      int cnt1 = (i - pre[j]) - cnt0;
+      if (cnt0 * cnt0 <= cnt1) {
+        int add = j - pre[j];
+        if (cnt1 - cnt0 * cnt0 + 1 < add)
+          add = cnt1 - cnt0 * cnt0 + 1;
+        ans += add;
+      }
+      j = pre[j];
+      cnt0++;
+    }
+  }
+  free(pre);
+  return ans;
+}
+
+int main() {
+  char *s1 = "00011", *s2 = "101101";
+  printf("%d\n", numberOfSubstrings(s1)); // expect: 5
+  printf("%d\n", numberOfSubstrings(s2)); // expect: 16
+}
diff --git a/count_num_substrings_dominant_one.py b/count_num_substrings_dominant_one.py
@@ -0,0 +1,37 @@
+# 3234. Count the Number of Substrings With Dominant Ones
+
+"""
+you are given a binary string 's'. return the number of substrings with
+dominant ones. a string has dominant ones if the number of ones in the string
+is greater than or equal to the sqaure of the number of zeroes in the string.
+"""
+
+
+class Solution(object):
+    def numberOfSubstrings(self, s):
+        """
+        :type s: str
+        :rtype: int
+        """
+        n, ans = len(s), 0
+        pre = [-1] * (n + 1)
+        for i in range(n):
+            if i == 0 or s[i - 1] == "0":
+                pre[i + 1] = i
+            else:
+                pre[i + 1] = pre[i]
+        for i in range(1, n + 1):
+            cnt0, j = 1 if s[i - 1] == "0" else 0, i
+            while j > 0 and cnt0 * cnt0 <= n:
+                cnt1 = (i - pre[j]) - cnt0
+                if cnt0 * cnt0 <= cnt1:
+                    ans += min(j - pre[j], cnt1 - cnt0 * cnt0 + 1)
+                j = pre[j]
+                cnt0 += 1
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.numberOfSubstrings(s="00011"))
+    print(obj.numberOfSubstrings(s="101101"))