##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1358.html

# 1358. Number of Substrings Containing All Three Characters (Medium)

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).


Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".


Example 3:

Input: s = "abc"
Output: 1


Constraints:

• 3 <= s.length <= 5 x 10^4
• s only consists of a, b or characters.

Related Topics:
String

## Solution 1. Sliding Window

// OJ: https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/
// Time: O(N)
// Space: O(1)
class Solution {
int cnt = {0};
bool valid() {
for (int n : cnt)
if (!n) return false;
return true;
}
public:
int numberOfSubstrings(string s) {
int L = 0, R = 0, N = s.size(), ans = 0;
while (R < N) {
if (!valid()) cnt[s[R++] - 'a']++;
while (valid()) {
ans += N - R + 1;
cnt[s[L++] - 'a']--;
}
}
return ans;
}
};

• class Solution {
public int numberOfSubstrings(String s) {
int substrings = 0;
int[] counts = new int;
int length = s.length();
int lettersCount = 0;
int start = 0, end = 0;
while (end < length) {
char c = s.charAt(end);
counts[c - 'a']++;
if (counts[c - 'a'] == 1)
lettersCount++;
while (lettersCount == 3) {
substrings += length - end;
char prevC = s.charAt(start);
start++;
counts[prevC - 'a']--;
if (counts[prevC - 'a'] == 0)
lettersCount--;
}
end++;
}
return substrings;
}
}

• // OJ: https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/
// Time: O(N)
// Space: O(1)
class Solution {
int cnt = {0};
bool valid() {
for (int n : cnt)
if (!n) return false;
return true;
}
public:
int numberOfSubstrings(string s) {
int L = 0, R = 0, N = s.size(), ans = 0;
while (R < N) {
if (!valid()) cnt[s[R++] - 'a']++;
while (valid()) {
ans += N - R + 1;
cnt[s[L++] - 'a']--;
}
}
return ans;
}
};

• class Solution:
def numberOfSubstrings(self, s: str) -> int:
d = {"a": -1, "b": -1, "c": -1}
ans = 0
for i, c in enumerate(s):
d[c] = i
ans += min(d["a"], d["b"], d["c"]) + 1
return ans