O(n) Solution Using Inclusion Exclusion Principle 🚀
IntuitionTo count the substrings that contain at least one occurrence of each of the characters 'a', 'b', and 'c', we can avoid checking every substring individ
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
To count the substrings that contain at least one occurrence of each of the characters 'a', 'b', and 'c', we can avoid checking every substring individually. Instead, we notice that if we know the total number of substrings and subtract those that are missing at least one required character, we obtain the answer. However, simply subtracting substrings missing each character individually will remove some substrings more than once (those composed entirely of a single character). We can correct this using the inclusion-exclusion principle.

# Approach
<!-- Describe your approach to solving the problem. -->
## Total Substrings
Calculate the total number of substrings of a string with length `n` using the formula:

```
totalPossible = (n * (n + 1)) / 2
```

---

## Count Substrings Missing a Character
For each character (`'a'`, `'b'`, and `'c'`), use the helper function `Not` to count the number of substrings that do **not** contain that character. This is done by:
- Iterating through the string.
- Identifying contiguous segments that do not include the character.
- Summing the number of substrings from each segment using the formula:
  
  ```
  (L * (L + 1)) / 2
  ```
  
  where `L` is the length of the contiguous segment.

---

## Count Substrings Composed of Only a Single Character
Use the helper function `CountOnly` to count substrings made up **exclusively** of a given character. These substrings were subtracted more than once in the previous step and need to be added back once.

---

## Apply Inclusion-Exclusion
The number of valid substrings that include all three characters is calculated as:

```
valid_substrings = totalPossible - (Not('a') + Not('b') + Not('c'))
                   + (CountOnly('a') + CountOnly('b') + CountOnly('c'))
```

---



# Complexity
## Time Complexity: O(n)
Each helper function traverses the string once, resulting in an overall linear time complexity.

## Space Complexity: O(1)
Only a fixed number of variables are used, so the space requirement is constant.

# Code
```cpp []
class Solution {
public:
    int CountOnly(string& s, char c)
    {
        int n = s.length();
        int ans = 0;
        int i = 0;
        int cnt = 0;
        while(i < n)
        {
            if(s[i] != c)
            {
                ans += (cnt * (cnt + 1) / 2);
                cnt = 0;
                i += 1;
            }
            else
            {
                cnt++;
                i += 1;
            }
        }
        ans += (cnt * (cnt + 1) / 2);
        return ans;
    }
    int Not(string& s, char c)
    {
        int n = s.length();
        int i = 0;
        int ans = 0;
        long long int cnt = 0;
        while(i < s.length())
        {
            if(s[i] == c)
            {
                ans += (cnt * (cnt + 1) / 2);
                cnt = 0;
                i += 1;
            }
            else
            {
                cnt++;
                i += 1;
            }
        }

        ans += (cnt * (cnt + 1) / 2);

        return ans;
    }

    // This was like inclusion exclusion principle
    int numberOfSubstrings(string s) {
        long long int n = s.length();
        long long int totalPossible = n * (n + 1) / 2;
        // ans = all - (notA + notB + notC) + (total only a strings + total only b strings + total only c strings)

        return totalPossible - (Not(s, 'a') + Not(s, 'b') + Not(s, 'c'))
        + (CountOnly(s, 'a') + CountOnly(s, 'b') + CountOnly(s, 'c'));
    }
};
```

### Happy Coding!
['String', 'C++']