Problem Description

You are given a string s consisting only of the characters 'a', 'b', and 'c'. Your task is to count the number of substrings of s that contain at least one occurrence of each of the three characters.

• Each substring must contain at least one 'a', one 'b', and one 'c'.
• Substrings are contiguous sequences of characters within s.
• The same substring can appear multiple times if it starts and ends at different positions.
• You do not need to list the substrings, only count them.

Constraints:
3 <= s.length <= 5 * 10^4
s contains only 'a', 'b', and 'c'.

Thought Process

The most straightforward way to solve this problem is to consider every possible substring of s and check if it contains all three characters. However, this brute-force approach would involve checking O(n²) substrings, and each check could take up to O(n) time, which would be too slow for large strings.

To optimize, we need a way to efficiently find, for each starting position, the earliest ending position where all three characters are present. If we can do this, we can count how many valid substrings start at each position without enumerating them all.

This leads to the idea of using a sliding window: we maintain a window (defined by two pointers) that expands until it contains all three characters, then we move the left pointer to look for new windows. This method allows us to efficiently count the valid substrings.

Solution Approach

We use the sliding window (two-pointer) technique with a character count map to keep track of the number of 'a', 'b', and 'c' in the current window.

1. Initialize: Set two pointers, left and right, both starting at 0. Use a hash map or array to keep count of each character in the current window.
2. Expand the window: Move the right pointer to the right, adding each character to the count.
3. Check window validity: When the window contains at least one of each character, count all substrings that start at left and end at any index from right to the end of the string. This is because adding more characters to the right will still include all three characters.
4. Count substrings: For each valid window, add len(s) - right to the answer (since every substring ending at or after right is valid).
5. Shrink the window: Move the left pointer to the right, decreasing the count of the character at left, and repeat the process.

This approach ensures that each character is processed at most twice (once when right moves forward, once when left moves forward), resulting in an O(n) solution.

Example Walkthrough

Consider the input s = "abcabc".

• Step 1: Start with left = 0, right = 0, and an empty count map.
• Step 2: Expand right to 0, 1, 2, adding 'a', 'b', 'c'. Now the window [0,2] contains all three characters.
• Step 3: Since the window is valid, all substrings starting at 0 and ending at 2 or later are valid. There are len(s) - right = 6 - 2 = 4 such substrings ("abc", "abca", "abcab", "abcabc").
• Step 4: Move left to 1, shrink the window, and repeat. Each time the window contains all three characters, count the valid substrings.

Continue this process for each starting position. The total count is the answer.

Time and Space Complexity

• Brute-force approach: O(n³) time (O(n²) substrings, O(n) to check each), O(1) space.
• Optimized sliding window approach: O(n) time, since each character is visited at most twice (once by left, once by right). O(1) space, as we only store counts for three characters.

Summary

The key insight is to use a sliding window to efficiently find valid substrings containing all three required characters. Instead of checking every possible substring, we count how many valid substrings start at each position by expanding and shrinking the window. This reduces the complexity from O(n³) to O(n), making it feasible for large inputs. The solution elegantly leverages the properties of substrings and the limited character set.

Code Implementation

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = {'a': 0, 'b': 0, 'c': 0}
        res = 0
        left = 0
        for right in range(len(s)):
            count[s[right]] += 1
            while all(count[char] > 0 for char in 'abc'):
                res += len(s) - right
                count[s[left]] -= 1
                left += 1
        return res
      

class Solution {
public:
    int numberOfSubstrings(string s) {
        int count[3] = {0, 0, 0};
        int res = 0, left = 0;
        for (int right = 0; right < s.size(); ++right) {
            count[s[right] - 'a']++;
            while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
                res += s.size() - right;
                count[s[left] - 'a']--;
                left++;
            }
        }
        return res;
    }
};
      

class Solution {
    public int numberOfSubstrings(String s) {
        int[] count = new int[3];
        int res = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'a']++;
            while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
                res += s.length() - right;
                count[s.charAt(left) - 'a']--;
                left++;
            }
        }
        return res;
    }
}
      

var numberOfSubstrings = function(s) {
    let count = {a:0, b:0, c:0};
    let res = 0, left = 0;
    for (let right = 0; right < s.length; right++) {
        count[s[right]]++;
        while (count['a'] > 0 && count['b'] > 0 && count['c'] > 0) {
            res += s.length - right;
            count[s[left]]--;
            left++;
        }
    }
    return res;
};