Beats 100% ✅| Simple Solution with Easy Explanation | Sliding Window | Time Complexity O(n) |
IntuitionThe problem requires us to count the number of substrings that contain at least one occurrence of 'a', 'b', and 'c'. Instead of generating all possible
# Intuition

The problem requires us to count the number of substrings that contain at least one occurrence of `'a'`, `'b'`, and `'c'`. Instead of generating all possible substrings (which would be inefficient), we use an optimized sliding window approach with last occurrence tracking to count the valid substrings efficiently in O(n) time complexity.



# Approach
 
1. **Tracking Last Occurrences**  
   - Maintain three variables `a`, `b`, and `c` to store the last seen indices of characters `'a'`, `'b'`, and `'c'`, respectively.  
   - Initialize them as `-1` since none of the characters have been encountered initially.  

2. **Iterate Through the String**  
   - Traverse the string character by character using a loop.  

3. **Update the Last Seen Index**  
   - When encountering `'a'`, update `a = i`.  
   - When encountering `'b'`, update `b = i`.  
   - When encountering `'c'`, update `c = i`.  

4. **Determine the Leftmost Valid Start Position**  
   - The minimum of `{a, b, c}` gives the earliest index where all three characters have been seen at least once.  

5. **Count Valid Substrings Ending at `i`**  
   - Every substring starting from any index `0` to `min(a, b, c)` and ending at `i` contains at least one `'a'`, `'b'`, and `'c'`.  
   - The number of such substrings is `1 + min(a, b, c)`.  

6. **Accumulate the Count**  
   - Add `1 + min(a, b, c)` to the total count of valid substrings.  

7. **Continue for All Characters**  
   - Repeat the process for every character in the string to ensure all substrings are counted efficiently.  

8. **Return the Final Count**  
   - After iterating through the string, return the accumulated count, which represents the total number of valid substrings.  


# Complexity
- Time complexity:
O(n)

- Space complexity:
O(1)

# Code
```cpp []
class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();

        // Initialize ans to store the total count of valid substrings
        int ans = 0;

        // a, b, c denote the last occurrence of characters 'a', 'b', and 'c' respectively
        int a = -1, b = -1, c = -1; 

        for (int i = 0; i < n; i++) {

            // Update the last occurrence of the current character
            if (s[i] == 'a') a = i;
            else if (s[i] == 'b') b = i;
            else c = i;

            // Calculate the number of substrings ending at index 'i' that contain at least one 'a', 'b', and 'c'

            ans += (1 + min({a, b, c})); //Ensures all valid substrings till index 'i' are counted
        }

        return ans;
    }
};

```
['String', 'Sliding Window', 'C++']