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 c 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[3] = {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;
}
};
Java
class Solution {
public int numberOfSubstrings(String s) {
int substrings = 0;
int[] counts = new int[3];
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;
}
}