Number of Substrings Containing All Three Characters

Leetcode Problem:

• Number of Substrings Containing All Three Characters

Summary

• The problem is to find the number of substrings in a given string that contain all three characters 'a', 'b', and 'c' at least once.

Approach

• The solution uses a sliding window approach with two pointers, 'l' and 'r', to track the current substring
• It iterates over the string with 'r' and expands the window to the right
• When all three characters are found in the window, it shrinks the window from the left until all characters are found again.

Complexity

• O(n) where n is the length of the string

Explanation

• The solution uses a 1D array 'cnt' to count the occurrences of each character
• The 'all_include' function checks if all three characters are present in the 'cnt' array
• The 'numberOfSubstrings' function iterates over the string with 'r' and expands the window to the right
• When all three characters are found in the window, it adds the number of substrings that can be formed with the current window to the 'ans' variable
• The window is then shrunk from the left until all characters are found again.

Solution Code:

class Solution {
    int cnt[256] = {0};
public:
    bool all_include(){
        return cnt['a'] > 0 && cnt['b'] > 0 && cnt['c'] > 0;
    }
    int numberOfSubstrings(string s) {
        int l = 0;
        int r = 0;
        int ans = 0;
        while(r < s.size()){
            cnt[s[r]]++;

            while(all_include() && l < r){
                ans += s.size() - r;
                cnt[s[l]]--;
                l++;
            }

            r++;

        }
        return ans;
    }
};