aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--num_substrings_3_char.c38
-rw-r--r--num_substrings_3_char.py31
2 files changed, 48 insertions, 21 deletions
diff --git a/num_substrings_3_char.c b/num_substrings_3_char.c
index 5a37858..f9e663a 100644
--- a/num_substrings_3_char.c
+++ b/num_substrings_3_char.c
@@ -1,29 +1,25 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+// 1358. Number of Substrings Containing All Three Characters
+#include "leetcode.h"
-int helper(char *s, int k) {
- int n = strlen(s), type = 0, left = 0, right = 0, res = 0;
- int *cn = calloc(3, sizeof(int));
- for (int right = 0; right < n; right++) {
- cn[s[right] - 'a']++;
- if (cn[s[right] - 'a'] == 1)
- type++;
- while (type > k) {
- cn[s[left] - 'a']--;
- if (!cn[s[left] - 'a'])
- type--;
- left++;
- }
- res += right - left + 1;
+/*
+ * given a string 's' consisting only of characters 'a', 'b', and 'c'. return
+ * the number of substrings containing at least one occurence of all these
+ * characters 'a', 'b', and 'c'.
+ */
+
+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;
}
- return res;
+ return ans;
}
-int numberOfSubstrings(char *s) { return helper(s, 3) - helper(s, 2); }
-
int main() {
- char s1[] = {"abcabc"}, s2[] = {"aaacb"}, s3[] = {"abc"};
+ 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
diff --git a/num_substrings_3_char.py b/num_substrings_3_char.py
new file mode 100644
index 0000000..13da3c4
--- /dev/null
+++ b/num_substrings_3_char.py
@@ -0,0 +1,31 @@
+# 1358. Number of Substrings Containing All Three Characters
+
+"""
+given a string 's' consisting only of characters 'a', 'b', and 'c'. return
+the number of substrings containing at least one occurence of all these
+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
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numberOfSubstrings(s="abcabc"))
+ print(obj.numberOfSubstrings(s="aaacb"))
+ print(obj.numberOfSubstrings(s="abc"))