Topics › Sliding Window and Two Pointers › Medium Problems

Number of Substrings Containing All Three Characters

Hard TUF ID 925 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a string s made only of the characters 'a', 'b' and 'c'. Return the number of substrings (contiguous, non-empty) that contain at least one occurrence of each of the three characters. Substrings at different positions count separately even if their text is equal.

Constraints: 3 ≤ |s| ≤ 5 × 10^4. The answer is at most n(n + 1) / 2 ≈ 1.25 × 10^9, which fits in an int (just barely; for longer inputs switch the counter to long).

Example 1

s = "abcabc"
answer = 10         // length 3: "abc", "bca", "cab", "abc"; length 4: 3; length 5: 2; length 6: 1

Example 2

s = "aaacb"
answer = 3          // "aaacb", "aacb", "acb"

Approach 1: Brute force

Intuition. Enumerate every substring by its start i and end j. Keep a three-entry seen table for the current start, mark s[j] as j grows, and count the substring whenever all three flags are set.

Algorithm.

1. For each i: reset seen = {false, false, false}.
2. For j = i ..: set seen[s[j] - 'a']; if all three are set, increment count.
3. Return count.

static int bruteForce(String s) {
    int n = s.length(), count = 0;
    for (int i = 0; i < n; i++) {
        boolean[] seen = new boolean[3];
        for (int j = i; j < n; j++) {
            seen[s.charAt(j) - 'a'] = true;
            if (seen[0] && seen[1] && seen[2]) count++;
        }
    }
    return count;
}

Complexity. Time O(n^2): all n(n + 1) / 2 substrings are visited. Space O(1).

Approach 2: Better, count all extensions at once

Intuition. The property “contains a, b and c” is monotonic in the end: if s[i..j] contains all three, so does s[i..j'] for every j' > j. So for a fixed start we only need the first end j that completes the set. Then the ends j, j + 1, ..., n - 1 all qualify, which is n - j substrings, and we can break immediately.

Algorithm.

1. For each i: reset seen.
2. For j = i ..: mark s[j]. When all three are set, add n - j and break.
3. Return count.

static int better(String s) {
    int n = s.length(), count = 0;
    for (int i = 0; i < n; i++) {
        boolean[] seen = new boolean[3];
        for (int j = i; j < n; j++) {
            seen[s.charAt(j) - 'a'] = true;
            if (seen[0] && seen[1] && seen[2]) {
                count += n - j;                    // ends j, j+1, ..., n-1 all work for this start
                break;
            }
        }
    }
    return count;
}

Complexity. Time O(n^2) in the worst case, for example "aaaa...abc" where every start must scan to the end. On typical inputs the break happens quickly. Space O(1).

Approach 3: Optimal, count by the right end using last positions

Intuition. Flip the viewpoint: fix the end r and ask how many starts make s[start..r] valid. The substring contains an 'a' if and only if start ≤ lastA, where lastA is the most recent index of 'a' at or before r. The same holds for 'b' and 'c'. So s[start..r] contains all three exactly when

start ≤ min(lastA, lastB, lastC)

The valid starts are 0, 1, ..., min(...), which is 1 + min(lastA, lastB, lastC) substrings. If some character has not appeared yet, its last index is -1, the minimum is -1, and the formula adds 0. No special case is needed.

This is still a sliding-window idea: the smallest of the three last positions is the right edge of the set of valid left ends, and it only moves forward as r grows.

Algorithm.

1. last = {-1, -1, -1}, count = 0.
2. For each r: set last[s[r] - 'a'] = r; add 1 + min(last[0], last[1], last[2]).
3. Return count.

static int optimal(String s) {
    int[] last = {-1, -1, -1};                     // last index of 'a', 'b', 'c' seen so far
    int count = 0;
    for (int r = 0; r < s.length(); r++) {
        last[s.charAt(r) - 'a'] = r;
        count += 1 + Math.min(last[0], Math.min(last[1], last[2]));   // adds 0 until all three have appeared
    }
    return count;
}

Dry run on s = "abcabc":

At r = 4, the three valid starts are 0, 1, 2, giving "abcab", "bcab" and "cab".

Complexity. Time O(n): one pass with constant work. Space O(1): three integers.

A more conventional window formulation gives the same answer. It keeps a count of each character in s[l..r] and, while all three counts are positive, adds n - r (every extension to the right is valid) and moves l forward. It counts each substring by its left end instead of its right end and also runs in O(n). The last-position formula is shorter and has no inner loop, which is why it is shown in full here.

Edge cases and pitfalls

• A character missing entirely. "aab" has no 'c', so the answer is 0; the optimal method keeps adding 1 + (-1) = 0.
• Empty or very short strings. Fewer than three characters can never qualify; the code returns 0 without special handling.
• Off-by-one in the count. Valid starts are 0..min, which is min + 1 values, not min.
• Counting by both ends. In Approach 2, add n - j (ends j through n - 1), and remember to break, otherwise the longer ends are counted twice.
• Other characters. The code indexes a three-entry table with s.charAt(j) - 'a', so any character other than a, b, c throws ArrayIndexOutOfBoundsException. If the required set grows to k letters, keep last with k entries and take the minimum over them, which costs O(n · k), or maintain the minimum with a counter of how many required letters have appeared.
• Overflow. The maximum count for n = 5 × 10^4 is about 1.25 × 10^9, inside int range. A longer string would need a long counter.

Related problems

• Count number of Nice subarrays also counts many subarrays per step instead of enumerating them.
• Binary Subarrays With Sum uses the “add r - l + 1 per right end” counting trick.
• Minimum Window Substring asks for the shortest window containing a set of required characters.
• Count Number of Substrings counts substrings with exactly k distinct characters.