Number of Substrings Containing All Three Characters — Medium Problem & Solution

s consists only of the characters 'a', 'b' and 'c'. Return the number of substrings that contain at least one of each.

Difficulty: Medium
Topics: Strings, Hash Table, Sliding Window
Asked at: Amazon, Google, Oracle
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

s consists only of the characters 'a', 'b' and 'c'.

Return the number of substrings that contain at least one of each.

Example 1

Input: s = "abcabc"
Output: 10
Explanation: Every substring of length 3 or more here qualifies.

Example 2

Input: s = "aaacb"
Output: 3
Explanation: "aaacb", "aacb" and "acb".

Example 3

Input: s = "abc"
Output: 1

Constraints

3 <= s.length <= 50000
s consists only of 'a', 'b' and 'c'.

How to solve Number of Substrings Containing All Three Characters

For each right end, the valid left ends form a prefix: the substring must reach back far enough to pick up all three characters, and the binding constraint is the most recent occurrence of the rarest one.

Approach

Track last[c], the most recent index of each of the three characters, all starting at -1.
At index i, update last[s[i]].
Add min(last) + 1 to the total — the number of valid starts.

Why it works

A substring [l, i] holds all three characters precisely when l <= last[c] for every c, because last[c] is the rightmost occurrence at or before i. The number of such l is min(last) + 1, and it is 0 while some character has not appeared, since min is then -1.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

The equivalent two-pointer formulation counts l rather than n - r, which is easy to get off by one.
Initialising last to 0 instead of -1 counts substrings before all three characters exist.
The total reaches about 1.25 · 10^9 at the upper limit, right at the edge of int.

Reference solution

Python

def numberOfSubstrings(s: str) -> int:
    last = [-1, -1, -1]
    total = 0
    for i, ch in enumerate(s):
        last[ord(ch) - 97] = i
        total += min(last) + 1
    return total

JavaScript

var numberOfSubstrings = function(s) {
    var last = [-1, -1, -1];
    var total = 0;
    for (var i = 0; i < s.length; i++) {
        last[s.charCodeAt(i) - 97] = i;
        total += Math.min(last[0], last[1], last[2]) + 1;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue