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;
 }