LeetCdoe 1358. Number of Substrings Containing All Three Characters

Question

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
2
3
4
5
6
7
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).

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".

Solution

It’s a sliding window question, but how to count the qualified string is the key. If we meet the requirement, the number of it would be n - end, which stands for string ends from end pointer to length of string. For example,abcabc, when we go the first char c, the number should be abc, abca, abcab, abcabc; total = 4 . Also, we use count array to record if it meets the requirement.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// time:O(n), space:O(1)
public int numberOfSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
int res = 0;
int[] count = new int[3];
int start = 0, end = 0;
int n = s.length();
while (end < n) {
count[s.charAt(end) - 'a']++;
while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
res += n - end;
count[s.charAt(start) - 'a']--;
start++;
}
end++;
}
return res;
}