leetcode

commit 058a9e781ea6cb0456b128b9af78d3cea10cde68
parent 8704ee5ba635a64f25efe6088971568bfff6df7c
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 30 Jun 2026 08:25:07 -0600

1358. number of substrings containing all three characters

Diffstat:
M
num_substrings_3_char.c
 | 
29
+++++++++++++++++++----------
M
num_substrings_3_char.py
 | 
25
++++++++++---------------

2 files changed, 29 insertions(+), 25 deletions(-)
diff --git a/num_substrings_3_char.c b/num_substrings_3_char.c
@@ -8,19 +8,28 @@
  */
 
 int numberOfSubstrings(char *s) {
-  int cnt[3] = {0}, ans = 0, i = 0, n = strlen(s);
-  for (int j = 0; j < n; ++j) {
-    ++cnt[s[j] - 'a'];
-    while (cnt[0] && cnt[1] && cnt[2])
-      --cnt[s[i++] - 'a'];
-    ans += i;
+  int vis[3] = {-1, -1, -1}, cnt = 0;
+  for (int i = 0; s[i] != '\0'; i++) {
+    vis[s[i] - 'a'] = i;
+    if (vis[0] != -1 && vis[1] != -1 && vis[2] != -1) {
+      int min = vis[0];
+      min = fmin(min, vis[1]);
+      min = fmin(min, vis[2]);
+      cnt += 1 + min;
+    }
   }
-  return ans;
+  return cnt;
 }
 
 int main() {
   char *s1 = "abcabc", *s2 = "aaacb", *s3 = "abc";
-  printf("%d\n", numberOfSubstrings(s1)); // expect: 10
-  printf("%d\n", numberOfSubstrings(s2)); // expect: 3
-  printf("%d\n", numberOfSubstrings(s3)); // expect: 1
+  int r1 = numberOfSubstrings(s1);
+  int r2 = numberOfSubstrings(s2);
+  int r3 = numberOfSubstrings(s3);
+  printf("%d\n", r1);
+  assert(r1 == 10);
+  printf("%d\n", r3);
+  assert(r2 == 3);
+  printf("%d\n", r3);
+  assert(r3 == 1);
 }
diff --git a/num_substrings_3_char.py b/num_substrings_3_char.py
@@ -7,21 +7,16 @@ characters 'a', 'b', and 'c'.
 """
 
 
-class Solution(object):
-    def numberOfSubstrings(self, s):
-        """
-        :type s: str
-        :rtype: int
-        """
-        cnt = {c: 0 for c in "abc"}
-        ans, i = 0, 0
-        for j in range(len(s)):
-            cnt[s[j]] += 1
-            while all(cnt.values()):
-                cnt[s[i]] -= 1
-                i += 1
-            ans += i
-        return ans
+class Solution:
+    def numberOfSubstrings(self, s: str) -> int:
+
+        lastSeen = [-1, -1, -1]
+        count = 0
+        for i in range(len(s)):
+            lastSeen[ord(s[i]) - ord("a")] = i
+            if lastSeen[0] != -1 and lastSeen[1] != -1 and lastSeen[2] != -1:
+                count += 1 + min(lastSeen[0], lastSeen[1], lastSeen[2])
+        return count
 
 
 if __name__ == "__main__":