🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
IntuitionThe problem requires counting the number of substrings that contain at least one occurrence of the characters 'a', 'b', and 'c'.
A brute-force approach

![1000115609.png](https://assets.leetcode.com/users/images/6828be2d-34bc-444e-aec9-1ed4d4246541_1741660093.9572225.png)





---

# **Intuition**
The problem requires counting the number of substrings that contain at least one occurrence of the characters **'a', 'b',** and **'c'**.  
A brute-force approach that generates all substrings and checks for these conditions would be **inefficient**.  
Instead, we use the **Sliding Window** technique to efficiently count valid substrings.

---

# **Approach**
1. **Sliding Window**:
   - Expand the window by moving the `right` pointer.
   - Maintain the **frequency count** of 'a', 'b', and 'c' in a **hashmap**.
   - If the window contains all three characters, it is **valid**.
2. **Counting Valid Substrings**:
   - If a valid window is found, **all substrings that start within this window and extend to the right are also valid**.
   - Count them as `s.length - right` (as all substrings formed by extending `right` are valid).
3. **Shrinking the Window**:
   - Move the `left` pointer **until the window is invalid** (i.e., missing a required character).
   - Continue counting valid substrings.

---

# **Complexity Analysis**
- **Time Complexity**: \(O(n)\) – Each character is processed at most twice (`right` expands, `left` shrinks).
- **Space Complexity**: \(O(1)\) – A hashmap of fixed size (`{'a', 'b', 'c'}`).

---


```dart []
class Solution {
  int numberOfSubstrings(String s) {
    Map<String, int> freq = {'a': 0, 'b': 0, 'c': 0};  
    int left = 0, ans = 0;

    for (int right = 0; right < s.length; right++) {
      freq[s[right]] = (freq[s[right]] ?? 0) + 1;

      // When all characters appear at least once, count valid substrings
      while (freq['a']! > 0 && freq['b']! > 0 && freq['c']! > 0) {
        ans += s.length - right; // Every substring ending at `right` is valid
        freq[s[left]] = freq[s[left]]! - 1;
        left++;
      }
    }
    
    return ans;
  }
}
```


```javascript []
var numberOfSubstrings = function(s) {
    let freq = { 'a': 0, 'b': 0, 'c': 0 };
    let left = 0, ans = 0;

    for (let right = 0; right < s.length; right++) {
        freq[s[right]] = (freq[s[right]] || 0) + 1;

        while (freq['a'] > 0 && freq['b'] > 0 && freq['c'] > 0) {
            ans += s.length - right;
            freq[s[left]]--;
            left++;
        }
    }

    return ans;
};
```


```java []
class Solution {
    public int numberOfSubstrings(String s) {
        int[] freq = new int[3]; // 'a' -> 0, 'b' -> 1, 'c' -> 2
        int left = 0, ans = 0;

        for (int right = 0; right < s.length(); right++) {
            freq[s.charAt(right) - 'a']++;

            while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {
                ans += s.length() - right;
                freq[s.charAt(left) - 'a']--;
                left++;
            }
        }

        return ans;
    }
}
```


```python []
def numberOfSubstrings(s: str) -> int:
    freq = {'a': 0, 'b': 0, 'c': 0}
    left = ans = 0

    for right in range(len(s)):
        freq[s[right]] += 1

        while all(freq[ch] > 0 for ch in "abc"):
            ans += len(s) - right
            freq[s[left]] -= 1
            left += 1

    return ans
```


```cpp []
#include <iostream>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int numberOfSubstrings(string s) {
        unordered_map<char, int> freq;
        int left = 0, ans = 0;

        for (int right = 0; right < s.size(); right++) {
            freq[s[right]]++;

            while (freq['a'] > 0 && freq['b'] > 0 && freq['c'] > 0) {
                ans += s.size() - right;
                freq[s[left]]--;
                left++;
            }
        }

        return ans;
    }
};
```


```go []
package main

import "fmt"

func numberOfSubstrings(s string) int {
    freq := map[byte]int{'a': 0, 'b': 0, 'c': 0}
    left, ans := 0, 0

    for right := 0; right < len(s); right++ {
        freq[s[right]]++

        for freq['a'] > 0 && freq['b'] > 0 && freq['c'] > 0 {
            ans += len(s) - right
            freq[s[left]]--
            left++
        }
    }

    return ans
}

func main() {
    fmt.Println(numberOfSubstrings("abcabc")) // Output: 10
}
```


```swift []
class Solution {
    func numberOfSubstrings(_ s: String) -> Int {
        var freq = ["a": 0, "b": 0, "c": 0]
        var left = 0, ans = 0
        let chars = Array(s)

        for right in 0..<chars.count {
            freq[String(chars[right]), default: 0] += 1

            while freq["a", default: 0] > 0 && freq["b", default: 0] > 0 && freq["c", default: 0] > 0 {
                ans += chars.count - right
                freq[String(chars[left])]! -= 1
                left += 1
            }
        }

        return ans
    }
}
```

---

# **Summary**
- **Sliding Window** efficiently finds valid substrings.
- **Optimized Counting** reduces redundant checks.

----


![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Hash Table', 'Swift', 'C', 'Sliding Window', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']