✅ Easy to Understand | Variable Sliding Window | Meta | Google | Detailed Video Explanation🔥
IntuitionThe problem requires us to count the number of substrings that contain at least one occurrence of all three characters ('a', 'b', and 'c').
A brute-for
# Intuition
The problem requires us to count the number of substrings that contain at least one occurrence of all three characters ('a', 'b', and 'c').  
A brute-force approach would involve checking all possible substrings, which would be inefficient for large inputs.  
Instead, we can use the **sliding window** (two-pointer) technique to efficiently find valid substrings.  

# Approach
1. **Use a sliding window** (two pointers `i` and `j`) to maintain a substring that contains at least one 'a', 'b', and 'c'.  
2. Maintain a frequency array `hash[3]` to count occurrences of 'a', 'b', and 'c' in the current window.  
3. Expand the window by moving `j` (right pointer) and updating the frequency of the current character.  
4. Whenever the window contains all three characters, calculate the number of valid substrings ending at `j` (`n - j` substrings).  
5. Shrink the window from the left (`i++`) while it remains valid to find more substrings.  
6. Repeat the process until `j` reaches the end of the string.  

This method ensures that we efficiently count all valid substrings in **O(n)** time without checking all possible substrings explicitly.  

# Complexity
- **Time complexity:**  
  The outer loop (expanding `j`) runs **O(n)**, and the inner loop (shrinking `i`) also runs **O(n)** in total.  
  Thus, the overall complexity is **O(n)**.

- **Space complexity:**  
  We only use an integer array of fixed size **3** (`hash[3]`), making the space complexity **O(1)**.


# Code
```java []
class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length(), ans = 0;
        int[] hash = new int[3]; // Array to store the frequency of 'a', 'b', and 'c'
        int i = 0, j = 0; // Two pointers for the sliding window approach

        for (; j < n; j++) { // Expand the right boundary of the window
            char ch = s.charAt(j);
            hash[ch - 'a']++; // Increase the count of the current character in the hash array

            // If the window contains at least one 'a', 'b', and 'c', start shrinking from the left
            while (valid(hash)) { 
                ans += (n - j); // Every valid substring from i to n contributes (n - j) substrings

                ch = s.charAt(i);
                hash[ch - 'a']--; // Remove the leftmost character from the window
                i++; // Shrink the window from the left
            }
        }
        return ans; // Return the total count of valid substrings
    }

    // Helper function to check if the window contains at least one 'a', 'b', and 'c'
    private boolean valid(int[] hash) {
        return hash[0] > 0 && hash[1] > 0 && hash[2] > 0;
    }
}

```

https://youtu.be/DAVhYDAKCRc


['Hash Table', 'String', 'Sliding Window', 'Java']