2 Easiest Optimal Solutions
APPROACH 1IntuitionThe problem asks for the number of substrings containing all three characters 'a', 'b', and 'c'. Using a sliding window approach, we can effi
# APPROACH 1
# Intuition
The problem asks for the number of substrings containing all three characters `'a'`, `'b'`, and `'c'`. Using a sliding window approach, we can efficiently count substrings that do not meet this requirement and subtract them from the total possible substrings.

# Approach
1. Compute the total number of substrings in the string, which is given by \( \text{totalComb} = \frac{n(n+1)}{2} \), where \( n \) is the length of the string.
2. Use a sliding window to find all substrings where the window contains at most two unique characters:
   - Maintain a frequency map (`m`) to count occurrences of characters within the current window.
   - Expand the window by incrementing the right pointer (`r`) and updating the frequency map.
   - If the map size exceeds 2, shrink the window from the left by incrementing the left pointer (`l`) and updating the frequency map.
3. For each valid window, count the number of substrings ending at the right pointer and add it to `lessEqual2`.
4. Subtract `lessEqual2` (substrings with at most two unique characters) from `totalComb` to get the desired result.

# Complexity
- **Time complexity:**  
  \( O(n) \), where \( n \) is the length of the string `s`.  
  - The left and right pointers traverse the string at most once.

- **Space complexity:**  
  \( O(1) \).  
  - The map `m` stores at most three characters at any time, so the space usage is constant.



# APPROACH 2
# Intuition 
The problem requires finding substrings that contain at least one occurrence of each character `'a'`, `'b'`, and `'c'`. Observing the problem, we realize that the substring's starting point depends on the earliest position among the last seen indices of `'a'`, `'b'`, and `'c'`.

# Approach
1. Use a sliding window approach where two pointers (`l` and `r`) represent the window.
2. Maintain a `lastSeen` array of size 3 to track the latest indices of `'a'`, `'b'`, and `'c'`:
   - `lastSeen[0]` for `'a'`, `lastSeen[1]` for `'b'`, and `lastSeen[2]` for `'c'`.
3. For each character in the string (`s[r]`), update its corresponding position in `lastSeen`.
4. The minimum value in `lastSeen` gives the earliest valid starting index for the substring. Use this to compute the count of valid substrings ending at the current position.
5. Accumulate the count and return the result.

# Complexity
- **Time complexity:**  
  \( O(n) \), where \( n \) is the length of the string `s`.  
  - We traverse the string once with a single loop.  
  - The `min` operation is \( O(1) \) as the size of `lastSeen` is constant.

- **Space complexity:**  
  \( O(1) \).  
  - The `lastSeen` array is of constant size (3 elements).  
  - No additional space dependent on the input size is used.



# Code
```cpp []
//OPTIMAL APPROCAH-2 T=O(2N)~O(N), S=O(3)~O(1)
class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        int count=0, l=0;
        vector<int>lastSeen = {-1,-1,-1};
        for(int r=0; r<n; r++){
            lastSeen[s[r]-'a'] = r;
            // if(lastSeen[0]!=-1 && lastSeen[1]!=-1 && lastSeen[2]!=-1){
                int mini = min(lastSeen[0],min(lastSeen[1],lastSeen[2]));
                count += 1+mini;
            // }
        }
        return count; 
    }
};
////OPTIMAL APPROCAH-1 T=O(2N)~O(N), S=O(3)~O(1)
// class Solution {
// public:
//     int numberOfSubstrings(string s) {
//         int n = s.size();
//         int totalComb = (1ll*n*(n+1))/2;
//         int lessEqual2=0, l=0;
//         unordered_map<char, int>m;
//         for(int r=0; r<n; r++){
//             m[s[r]]++;
//             while(m.size()>2){
//                 m[s[l]]--;
//                 if(m[s[l]]==0)
//                     m.erase(s[l]);
//                 l++;
//             }
//             lessEqual2 += r-l+1;
//         }
//     return totalComb-lessEqual2;
//     }
// };
//BRUTE FORCE: T=O(N^2), S=O(3);
// class Solution {
// public:
//     int numberOfSubstrings(string s) {
//         int count = 0;
//         for(int i=0; i<s.size(); i++){
//             unordered_map<char, int>m;
//             for(int j=i; j<s.size(); j++){
//                 m[s[j]]++;
//                 if(m.size() == 3){
//                     count += s.size()-j;
//                     break;
//                 }
//             }
//         }
//         return count;
//     }
// };
```
['Hash Table', 'String', 'Sliding Window', 'C++']