Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Number of Substrings Containing All Three Characters

MEDIUMProblemSolveExternal Links

Description

Given a string s that consists only of the characters 'a', 'b', and 'c', return the total number of substrings of s that contain at least one occurrence of each of these three characters.

A substring is any contiguous sequence of characters within the string. For a substring to be counted, it must include at least one 'a', at least one 'b', and at least one 'c'.

Examples

Example 1

Input: s = "abcabc"

Output: 10

Explanation: The 10 substrings that contain at least one 'a', one 'b', and one 'c' are:

  • Starting at index 0: "abc", "abca", "abcab", "abcabc"
  • Starting at index 1: "bca", "bcab", "bcabc"
  • Starting at index 2: "cab", "cabc"
  • Starting at index 3: "abc"

Every other substring (like "ab", "bc", "a") is missing at least one of the three required characters.

Example 2

Input: s = "aaacb"

Output: 3

Explanation: Only three substrings contain all three characters:

  • "aaacb" (indices 0 to 4)
  • "aacb" (indices 1 to 4)
  • "acb" (indices 2 to 4)

Notice that all valid substrings must extend to the very end of the string because 'b' only appears at the last position.

Example 3

Input: s = "abc"

Output: 1

Explanation: The entire string "abc" is the only substring that contains all three characters. No shorter substring can contain all of 'a', 'b', and 'c'.

Constraints

  • 3 ≤ s.length ≤ 5 × 10^4
  • s only consists of characters 'a', 'b', and 'c'.

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to examine every possible substring and check whether it contains all three characters.

Imagine you have a magnifying glass and you are scanning through the string. You pick a starting position, then gradually extend your view to the right one character at a time. As you extend, you keep a mental tally of how many 'a's, 'b's, and 'c's you have seen within your current view.

The moment your tally shows at least one of each character, you know your current substring is valid. But here is the key optimization: once a substring from position i to position j contains all three characters, then every longer substring from i to any position beyond j will also be valid, because adding more characters cannot remove the ones already present. So instead of checking each extension individually, you can count all of them at once — there are exactly n - j such substrings — and move on to the next starting position.

Step-by-Step Explanation

Let's trace through with s = "aaacb" (Example 2), where n = 5:

Step 1: Fix starting index i = 0. Initialize character counts: count_a = 0, count_b = 0, count_c = 0.

Step 2: Expand to j = 0, s[0] = 'a'. count_a = 1. We have {a} but are missing 'b' and 'c'. Not valid yet.

Step 3: Expand to j = 1, s[1] = 'a'. count_a = 2. Still only {a}. Keep expanding.

Step 4: Expand to j = 2, s[2] = 'a'. count_a = 3. Still only {a}.

Step 5: Expand to j = 3, s[3] = 'c'. count_c = 1. Now we have {a, c} but still missing 'b'.

Step 6: Expand to j = 4, s[4] = 'b'. count_b = 1. Now we have {a, b, c} — all three present! Since every extension from j = 4 onward is valid, add n - j = 5 - 4 = 1 valid substring. result = 1. Break inner loop.

Step 7: Fix i = 1. Reset counts. Expand j from 1 to 4. At j = 4, counts are {a:2, b:1, c:1} — all present. Add n - 4 = 1. result = 2.

Step 8: Fix i = 2. Expand j from 2 to 4. At j = 4, counts are {a:1, b:1, c:1} — all present. Add 1. result = 3.

Step 9: Fix i = 3. Expand j from 3 to 4. Counts are {c:1, b:1}. Missing 'a'. No valid substrings from this start.

Step 10: Fix i = 4. Only one character 'b'. Missing 'a' and 'c'. No valid substrings.

Result: 3 valid substrings.

Brute Force — Expanding Window for Each Starting Position — Watch how for each starting index i, we expand j rightward while tracking character counts. Once all three characters appear, every further extension is automatically valid.

Algorithm

  1. Initialize result = 0.
  2. For each starting index i from 0 to n - 1:
    • Reset character counts: count_a = count_b = count_c = 0.
    • For each ending index j from i to n - 1:
      • Increment the count for character s[j].
      • If all three counts are at least 1:
        • Add n - j to result (all extensions from j to n-1 are valid).
        • Break the inner loop (no need to keep expanding from this i).
  3. Return result.

Code

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int count[3] = {0, 0, 0};
            for (int j = i; j < n; j++) {
                count[s[j] - 'a']++;
                if (count[0] >= 1 && count[1] >= 1 && count[2] >= 1) {
                    result += (n - j);
                    break;
                }
            }
        }
        
        return result;
    }
};
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        result = 0
        
        for i in range(n):
            count = {'a': 0, 'b': 0, 'c': 0}
            for j in range(i, n):
                count[s[j]] += 1
                if count['a'] >= 1 and count['b'] >= 1 and count['c'] >= 1:
                    result += (n - j)
                    break
        
        return result
class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int[] count = new int[3];
            for (int j = i; j < n; j++) {
                count[s.charAt(j) - 'a']++;
                if (count[0] >= 1 && count[1] >= 1 && count[2] >= 1) {
                    result += (n - j);
                    break;
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times (one for each starting index). For each starting index, the inner loop may scan up to n characters in the worst case before finding all three characters (or reaching the end). This gives a worst-case of n × n = O(n²) operations. The worst case occurs when one character appears only near the end of the string, forcing the inner loop to scan most of the array for each starting position.

Space Complexity: O(1)

We use only a fixed-size count array of 3 elements (for characters 'a', 'b', 'c') and a few integer variables. This does not grow with the input size.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity. With n up to 5 × 10^4, this means up to 2.5 × 10^9 operations in the worst case — far too slow for typical time limits.

The fundamental inefficiency is that we restart the search from scratch for every starting position. When we move from i to i + 1, we throw away all the information we gathered about character positions during the previous scan. We already know where each character appears, yet we rescan from the beginning each time.

The key insight for improvement: instead of asking "for this starting position, where do I first see all three characters?" we can flip the question to "for each ending position, how many starting positions yield a valid substring?" If we track the most recent position of each character as we scan left to right, we can answer this question in O(1) for each position — reducing the total time from O(n²) to O(n).

Optimal Approach - Last Position Tracking

Intuition

Instead of checking substrings one by one, let us think about the problem from a different angle. As we scan through the string from left to right, for each position i we ask: how many valid substrings end exactly at position i?

A substring ending at position i is valid if it contains at least one 'a', one 'b', and one 'c'. For this to happen, the substring must start early enough to include the most recent occurrence of every character.

Imagine you are reading the string character by character. You keep a mental note of where you last saw each of the three characters. At any point, the "bottleneck" character is the one you saw least recently — its last-seen position is the smallest. Any substring that starts at or before this bottleneck position and ends at the current position will contain all three characters.

For example, if you are at position 5 and you last saw 'a' at position 3, 'b' at position 4, and 'c' at position 2, then the bottleneck is 'c' at position 2. Valid substrings ending at position 5 can start at positions 0, 1, or 2 — that is min(3, 4, 2) + 1 = 3 valid substrings.

The formula is elegant: for each position i, add min(last_a, last_b, last_c) + 1 to the answer. If any character has not been seen yet (last position is -1), the minimum is -1, and -1 + 1 = 0 — correctly contributing nothing.

Step-by-Step Explanation

Let's trace through with s = "abcabc" (Example 1), where n = 6:

Step 1: Initialize last = {a: -1, b: -1, c: -1}, answer = 0. All characters are marked as "not yet seen" with -1.

Step 2: i = 0, s[0] = 'a'. Update last_a = 0. min(0, -1, -1) = -1. Add -1 + 1 = 0. answer = 0.
Reasoning: We have seen 'a' but not 'b' or 'c'. No valid substrings end here.

Step 3: i = 1, s[1] = 'b'. Update last_b = 1. min(0, 1, -1) = -1. Add 0. answer = 0.
Reasoning: We have 'a' and 'b' but still no 'c'. Still no valid substrings.

Step 4: i = 2, s[2] = 'c'. Update last_c = 2. min(0, 1, 2) = 0. Add 0 + 1 = 1. answer = 1.
Reasoning: All three characters seen! The bottleneck is 'a' at position 0. Substrings starting at position 0 through 0 and ending at 2 are valid: "abc". That is 1 substring.

Step 5: i = 3, s[3] = 'a'. Update last_a = 3. min(3, 1, 2) = 1. Add 1 + 1 = 2. answer = 3.
Reasoning: The bottleneck is now 'b' at position 1. Valid substrings ending at index 3: "abca" (start 0) and "bca" (start 1). That is 2 substrings.

Step 6: i = 4, s[4] = 'b'. Update last_b = 4. min(3, 4, 2) = 2. Add 2 + 1 = 3. answer = 6.
Reasoning: Bottleneck is 'c' at position 2. Valid substrings ending at index 4: "abcab" (start 0), "bcab" (start 1), "cab" (start 2). That is 3 substrings.

Step 7: i = 5, s[5] = 'c'. Update last_c = 5. min(3, 4, 5) = 3. Add 3 + 1 = 4. answer = 10.
Reasoning: Bottleneck is 'a' at position 3. Valid substrings ending at index 5: "abcabc" (start 0), "bcabc" (start 1), "cabc" (start 2), "abc" (start 3). That is 4 substrings.

Result: answer = 10.

Last Position Tracking — Counting Valid Substrings in One Pass — Watch how tracking the most recent position of each character lets us instantly compute how many valid substrings end at each position, without any inner loop.

Algorithm

  1. Create a dictionary last mapping each character ('a', 'b', 'c') to -1, indicating none have been seen yet.
  2. Initialize answer = 0.
  3. For each index i from 0 to n - 1:
    • Update last[s[i]] = i to record the most recent position of the current character.
    • Compute min_last = min(last['a'], last['b'], last['c']).
    • Add min_last + 1 to answer. If any character hasn't appeared yet, min_last is -1, contributing 0.
  4. Return answer.

Code

class Solution {
public:
    int numberOfSubstrings(string s) {
        int last[3] = {-1, -1, -1};
        int result = 0;
        
        for (int i = 0; i < (int)s.size(); i++) {
            last[s[i] - 'a'] = i;
            result += min({last[0], last[1], last[2]}) + 1;
        }
        
        return result;
    }
};
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        last = {'a': -1, 'b': -1, 'c': -1}
        result = 0
        
        for i, char in enumerate(s):
            last[char] = i
            result += min(last['a'], last['b'], last['c']) + 1
        
        return result
class Solution {
    public int numberOfSubstrings(String s) {
        int[] last = {-1, -1, -1};
        int result = 0;
        
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
            result += Math.min(last[0], Math.min(last[1], last[2])) + 1;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make a single pass through the string of length n. At each position, we perform O(1) work: one dictionary update, one minimum of three values, and one addition. The total is exactly n iterations × O(1) per iteration = O(n).

Space Complexity: O(1)

We use a fixed-size dictionary (or array) with exactly 3 entries to store the last-seen positions of 'a', 'b', and 'c'. This space does not depend on the input size. The only other variables are the loop counter and the running total, both constant space.