# Number of Substrings Containing All Three Characters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-substrings-containing-all-three-characters)
Canonical: https://scaleengineer.com/dsa/problems/number-of-substrings-containing-all-three-characters
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Given a string `s` consisting only of characters _a_, _b_ and _c_.

Return the number of substrings containing **at least** one occurrence of all these characters _a_, _b_ and _c_.

**Example 1:**

**Input:** s = "abcabc"
**Output:** 10
**Explanation:** The substrings containing at least one occurrence of the characters _a_, _b_ and _c are "_abc_", "_abca_", "_abcab_", "_abcabc_", "_bca_", "_bcab_", "_bcabc_", "_cab_", "_cabc_"_ and _"_abc_"_ (**again**)_._ 

**Example 2:**

**Input:** s = "aaacb"
**Output:** 3
**Explanation:** The substrings containing at least one occurrence of the characters _a_, _b_ and _c are "_aaacb_", "_aacb_"_ and _"_acb_"._

**Example 3:**

**Input:** s = "abc"
**Output:** 1

**Constraints:**

* `3 <= s.length <= 5 x 10^4`
* `s` only consists of _a_, _b_ or _c_ characters.

# Approaches
## Brute Force Enumeration
The most straightforward approach is to generate every possible substring of the input string `s` and then, for each one, check if it contains at least one 'a', one 'b', and one 'c'. We can use two nested loops to define the start and end points of all substrings and a helper function to validate each one.
**Time:** O(n³). There are O(n²) substrings. For each substring, we perform a check that can take up to O(n) time in the worst case. This leads to a total time complexity of O(n² * n) = O(n³). · **Space:** O(n). In the worst case, a substring of length `n` is created, requiring O(n) space. The check itself can be done with O(1) space, but the substring creation dominates.
**Pros:** Simple to understand and implement.; Correctly solves the problem for very small inputs.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
This method systematically checks every single substring. The outer loop fixes the starting character of the substring, and the inner loop extends the substring one character at a time to the right. For each generated substring, a separate check is performed to see if it meets the criteria of containing all three characters 'a', 'b', and 'c'.

```java
class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isValid(s.substring(i, j + 1))) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isValid(String sub) {
        boolean hasA = false;
        boolean hasB = false;
        boolean hasC = false;
        for (char c : sub.toCharArray()) {
            if (c == 'a') hasA = true;
            if (c == 'b') hasB = true;
            if (c == 'c') hasC = true;
            if (hasA && hasB && hasC) return true;
        }
        return false;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use a nested loop to generate all substrings. The outer loop `i` iterates from 0 to `n-1` (start index).
3. The inner loop `j` iterates from `i` to `n-1` (end index).
4. For each substring `s.substring(i, j+1)`, create a helper function `isValid(substring)`.
5. The `isValid` function checks if the substring contains 'a', 'b', and 'c'. This can be done by iterating through the substring and using a `Set` or three boolean flags.
6. If `isValid` returns true, increment `count`.
7. After the loops complete, return `count`.

## Optimized Brute Force
This approach improves upon the naive brute force method by optimizing the validation step. Instead of re-scanning each substring from scratch, we can maintain a running count of the characters 'a', 'b', and 'c' as we extend the substring from a fixed starting point.
**Time:** O(n²). We still have two nested loops. Although we have an optimization with `break`, the worst-case scenario (e.g., a string like 'aaaa...aaabc') still requires iterating through most of the O(n²) pairs. · **Space:** O(1). We only use a constant-size array for frequency counts, regardless of the input string size.
**Pros:** More efficient than the naive O(n³) brute force.; Reduces redundant computations by reusing the frequency count.
**Cons:** Still too slow for the given constraints, leading to 'Time Limit Exceeded'.
### Explanation
We iterate through all possible starting positions `i`. For each `i`, we iterate from `j = i` to the end of the string, maintaining a count of characters 'a', 'b', and 'c' for the substring `s[i...j]`. Once the substring `s[i...j]` contains all three characters, we know it's a valid substring. Furthermore, any substring starting at `i` and ending after `j` (i.e., `s[i...j+1]`, `s[i...j+2]`, etc.) will also be valid. There are `n - j` such substrings. We can add this number to our total count and break the inner loop to move to the next starting position `i`.

```java
class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            int[] freq = new int[3]; // 0 for 'a', 1 for 'b', 2 for 'c'
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                if (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {
                    // All substrings from s[i...j] to s[i...n-1] are valid
                    count += (n - j);
                    break; // Move to the next starting point i
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use an outer loop `i` from 0 to `n-1` to fix the starting point of the substring.
3. For each `i`, initialize a frequency count (e.g., an array `int[3]`) for characters 'a', 'b', 'c'.
4. Use an inner loop `j` from `i` to `n-1` to extend the substring to the right.
5. In the inner loop, update the frequency count for the character `s.charAt(j)`.
6. After updating, check if the counts for 'a', 'b', and 'c' are all greater than 0.
7. If they are, it means the substring `s.substring(i, j+1)` is valid. From this point on, any further extension of the substring from this `i` will also be valid. So we can add the remaining length `n-j` to the count and break the inner loop.
8. Return `count` after the loops.

## Sliding Window
A much more efficient approach uses the sliding window technique. The core idea is that if a substring `s[i...j]` is valid (contains 'a', 'b', 'c'), then any larger substring that contains it, like `s[i...k]` where `k > j`, is also valid. We can use this property to count valid substrings in linear time by efficiently expanding and shrinking a window over the string.
**Time:** O(n). Both `left` and `right` pointers traverse the string at most once. Each character is added to and removed from the window once, leading to linear time complexity. · **Space:** O(1). We use a constant-size array for frequency counts.
**Pros:** Optimal time complexity of O(n).; Efficiently solves the problem within the given constraints.; Uses constant extra space.
**Cons:** The logic of counting `n - right` and shrinking the window can be slightly less intuitive on first sight compared to brute-force methods.
### Explanation
We maintain a window `[left, right]` and a frequency count of characters within it. We expand the window by moving `right`. Once the window contains 'a', 'b', and 'c', we know that the current substring `s[left...right]` is valid. Crucially, any substring that starts at `left` and ends at or after `right` is also valid. There are `n - right` such substrings. We add this to our total count. Then, we try to find a new, smaller valid window by shrinking it from the left (incrementing `left`) and updating the frequency count. We repeat this process until the window is no longer valid, at which point we continue expanding with `right`.

```java
class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        int left = 0;
        long count = 0;
        int[] freq = new int[3]; // 0 for 'a', 1 for 'b', 2 for 'c'

        for (int right = 0; right < n; right++) {
            freq[s.charAt(right) - 'a']++;
            
            // Once the window is valid, for this fixed 'right', any substring
            // starting from the current 'left' up to 'right' is a valid start.
            // But the logic here is different: we shrink the window.
            while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {
                // If s[left...right] is a valid window, then s[left...right], 
                // s[left...right+1], ..., s[left...n-1] are all valid substrings.
                // There are n - right such substrings.
                count += (n - right);
                
                // Now, we shrink the window from the left to see if we can find
                // another valid window with a new 'left'.
                freq[s.charAt(left) - 'a']--;
                left++;
            }
        }
        return (int)count;
    }
}
```
### Algorithm
1. Initialize two pointers, `left = 0`, a result counter `count = 0`, and a frequency map `freq` (e.g., an `int[3]` array).
2. Iterate with a `right` pointer from 0 to `n-1` to expand the window.
3. In each iteration, add `s.charAt(right)` to the window by incrementing its count in `freq`.
4. Enter a `while` loop that runs as long as the current window `s[left...right]` is valid (i.e., `freq['a'] > 0`, `freq['b'] > 0`, and `freq['c'] > 0`).
5. Inside the `while` loop, we've found a minimal valid substring `s[left...right]`. Any substring starting at `left` and ending at `right` or later will also be valid. There are `n - right` such substrings. Add this number to `count`.
6. To find other valid substrings, shrink the window from the left: decrement the frequency of `s.charAt(left)` and increment `left`.
7. The `while` loop continues to shrink the window as long as it remains valid.
8. After the main loop over `right` finishes, return `count`.

## Efficient One-Pass Approach with Last Seen Indices
This is an elegant and highly efficient O(n) solution that can be seen as a specialized version of the sliding window. Instead of maintaining a frequency count and two pointers, we simplify the state by just keeping track of the last seen indices of 'a', 'b', and 'c'. This allows for a very clean single-pass solution.
**Time:** O(n). The algorithm consists of a single loop that iterates through the string once. · **Space:** O(1). We only use a constant-size array (`lastSeen`) to store three indices.
**Pros:** Optimal O(n) time complexity and O(1) space complexity.; Very concise and implemented in a single, clean pass.; Arguably the most elegant and efficient solution.
**Cons:** The counting logic (`min(...) + 1`) might require a moment of thought to fully grasp its correctness.
### Explanation
We iterate through the string, and for each position `i`, we update the last seen index of the character `s.charAt(i)`. As soon as we have seen all three characters, we can calculate how many valid substrings *end* at the current position `i`. A substring `s[j...i]` is valid if it contains all three characters. This is guaranteed if `j` is less than or equal to the indices of the most recent 'a', 'b', and 'c'. Therefore, `j` can be any index from 0 up to `min(last_a, last_b, last_c)`. The number of such valid starting points `j` is `min(last_a, last_b, last_c) + 1`. By summing this value for each `i` in the string, we get the total count.

```java
class Solution {
    public int numberOfSubstrings(String s) {
        // lastSeen[0] for 'a', lastSeen[1] for 'b', lastSeen[2] for 'c'
        int[] lastSeen = {-1, -1, -1};
        int count = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            lastSeen[s.charAt(i) - 'a'] = i;
            
            // If we have not seen all three characters yet, we can't form a valid substring.
            if (lastSeen[0] == -1 || lastSeen[1] == -1 || lastSeen[2] == -1) {
                continue;
            }
            
            // Find the minimum index among the last seen positions of a, b, and c.
            // This index is the leftmost boundary of the shortest valid substring ending at i.
            int minIndex = Math.min(lastSeen[0], Math.min(lastSeen[1], lastSeen[2]));
            
            // Any substring starting from index 0 up to minIndex and ending at i will be valid.
            // The number of such substrings is minIndex + 1.
            count += (minIndex + 1);
        }
        
        return count;
    }
}
```
### Algorithm
1. Initialize an array `lastSeen` of size 3 with -1, to store the most recent index of 'a', 'b', and 'c'.
2. Initialize a counter `count = 0`.
3. Iterate through the string with an index `i` from 0 to `n-1`.
4. At each character `s.charAt(i)`, update the corresponding index in `lastSeen` to `i`.
5. After updating, check if we have seen all three characters (i.e., none of the indices in `lastSeen` are -1).
6. If so, a valid substring ending at `i` must start at or before the character that appeared least recently. This position is `min(lastSeen[0], lastSeen[1], lastSeen[2])`.
7. Any substring starting from index 0 up to this minimum index, and ending at `i`, will be valid. The number of such starting positions is `min(lastSeen) + 1`.
8. Add this number to our total `count`.
9. After the loop finishes, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfSubstrings(String s) {
    int[] d = new int[]{-1, -1, -1};
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      d[c - 'a'] = i;
      ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfSubstrings(string s) {
    int d[3] = {-1, -1, -1};
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
      d[s[i] - 'a'] = i;
      ans += min(d[0], min(d[1], d[2])) + 1;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfSubstrings(self, s: str) -> int: d = {"a": - 1, "b": - 1, "c": - 1} ans = 0 for i, c in enumerate(s): d[c] = i ans += min(d["a"], d["b"], d["c"]) + 1 return ans

```