Sliding Window Magic: Count Substrings Containing 'a', 'b', and 'c' Efficiently!
IntuitionThe problem requires us to count the number of substrings that contain at least one occurrence of each of the characters 'a', 'b', and 'c'. The most ef
# Intuition  
The problem requires us to count the number of substrings that contain at least one occurrence of each of the characters 'a', 'b', and 'c'. The most efficient way to do this is by using a sliding window approach, which allows us to dynamically track valid substrings while minimizing unnecessary computations.  

# Approach  
1. **Sliding Window Technique**:  
   - Maintain two pointers, `i` and `j`, to represent a window in the string.
   - Use a frequency array `mp` of size 3 to track the counts of 'a', 'b', and 'c' in the current window.
   - Expand the window by increasing `j` and updating `mp` accordingly.
   - Once the window contains at least one occurrence of each character, all substrings starting from `i` to `n` and ending at `j` are valid.
   - Shrink the window from the left (`i++`) to check for other valid substrings while ensuring that all three characters are still present.

2. **Counting Valid Substrings Efficiently**:  
   - Every time a valid substring is found (i.e., the window contains at least one 'a', 'b', and 'c'), count the number of possible substrings using `(n - j)`.
   - This is because fixing `j` at a valid position means that any ending index from `j` to `n-1` still forms a valid substring.

# Complexity  
- **Time Complexity**:  
  - The outer loop runs `O(n)` times as `j` traverses the string.  
  - The inner loop also runs `O(n)` times in total since each character is processed once when expanding and once when contracting the window.  
  - Hence, the overall complexity is **O(n)**.

- **Space Complexity**:  
  - We use an array of size 3 (`mp`) to store character counts, which is **O(1)**.  
  - Other variables take constant space, so the overall space complexity remains **O(1)**.

# Code
```cpp []
class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.length();
        int i=0;
        int j=0;
        vector<int> mp(3,0);
        int res=0;
        while(j<n){
            char ch=s[j];
            mp[ch-'a']++;
            while(mp[0]>0 && mp[1]>0 && mp[2]>0){
                res+=(n-j);
                mp[s[i]-'a']--;
                i++;
            }
            j++;
        }
        return res;

    }
};
```
![UpVote.jpg](https://assets.leetcode.com/users/images/6a50623f-370b-4b4c-b2db-20702d03ce62_1741715577.2701468.jpeg)


['C++']