Number of Substrings Containing All Three Characters

medium sliding window counting

Problem

You are given a string s built only from the letters a, b and c (3 ≤ |s| ≤ 5·10⁴). Count how many substrings of s contain at least one a, at least one b and at least one c.

With up to ~1.25 billion substrings possible, checking each one is far too slow — a sliding window counts them all in a single pass.

Inputs = "abcabc"

Output10

The valid substrings are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and the second "abc".

s (letters a, b, c only)

def number_of_substrings(s):
    count = {'a': 0, 'b': 0, 'c': 0}
    left = 0
    ans = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while count['a'] > 0 and count['b'] > 0 and count['c'] > 0:
            count[s[left]] -= 1
            left += 1
        ans += left
    return ans

function numberOfSubstrings(s) {
  const count = { a: 0, b: 0, c: 0 };
  let left = 0, ans = 0;
  for (let right = 0; right < s.length; right++) {
    count[s[right]]++;
    while (count.a > 0 && count.b > 0 && count.c > 0) {
      count[s[left]]--;
      left++;
    }
    ans += left;
  }
  return ans;
}

int numberOfSubstrings(String s) {
    int[] count = new int[3];
    int left = 0, ans = 0;
    for (int right = 0; right < s.length(); right++) {
        count[s.charAt(right) - 'a']++;
        while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
            count[s.charAt(left) - 'a']--;
            left++;
        }
        ans += left;
    }
    return ans;
}

int numberOfSubstrings(string s) {
    int count[3] = {0, 0, 0};
    int left = 0, ans = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        count[s[right] - 'a']++;
        while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
            count[s[left] - 'a']--;
            left++;
        }
        ans += left;
    }
    return ans;
}

Explanation

The key insight: fix where a substring ends. If s[i..right] contains all three letters, then starting even earlier — s[i-1..right], s[i-2..right], and so on — only adds letters, so those substrings contain all three too. For each right, the valid starts therefore form a prefix 0, 1, …, k, and all we need is how long that prefix is.

A sliding window finds it. Move right one letter at a time, incrementing that letter's count. Whenever the window s[left..right] holds all three letters, it is "too valid": drop s[left] and advance left, repeating until one letter's count hits zero. The window now barely misses being valid — which means every start strictly before left still works. So we simply add left to the answer after each step of right.

Walking through s = "abcabc": at right = 0, 1 the window lacks letters, left stays 0, nothing is added. At right = 2 the window "abc" is complete, so we drop the a at index 0; now left = 1 and we add 1 (the substring "abc"). At right = 3 the a returns, we drop the b, left = 2, add 2 → total 3. At right = 4 we drop the c, left = 3, add 3 → 6. At right = 5 we drop the a at index 3, left = 4, add 4 → 10.

Why is this fast? right moves forward n times, and left only ever moves forward, at most n times across the whole run. Each character is added to the window once and removed at most once, so the total work is O(n) even though there is a loop inside a loop.

Space is O(1): just three counters, two pointers and the running answer. Note the answer counts substrings, not windows — the shrink step is exactly what converts "the window is valid" into "left different substrings ending here are valid".

Time: O(n) Space: O(1)