diff options
-rw-r--r-- | num_substrings_3_char.c | 38 | ||||
-rw-r--r-- | num_substrings_3_char.py | 31 |
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")) |