AlgoViz
HomeSliding Window

Number of Substrings Containing All Three Characters

Hard

Count from the last valid start

Problem

Count substrings that contain at least one each of 'a', 'b', and 'c'.

In simple words

For each end, the earliest of the last a/b/c positions tells how many valid starts there are.

The idea

Track the most recent index of each of a, b and c. For every right edge, the smallest of those three indices is the furthest left a valid substring can start, so it contributes (min + 1) substrings ending here.

The trick

  • Every substring extending a valid one to the left is also valid — that is why counting is O(1) per position.
  • Keep last-seen indices, initialised to -1.
  • O(n) total.
a
b
c
a
b
c
0
1
2
3
4
5

Step 1 of 23. Brute force: check every substring for containing a, b and c. Values: a, b, c, a, b, c.

1/23
Brute force
timeO(n²)spaceO(1)

Every substring.

1for (let i = 0; i < n; i++) {2  const have = new Set();3  for (let j = i; j < n; j++) {4    have.add(s[j]);5    if (have.size === 3) count++;6  }7}

Input

array
[a, b, c, a, b, c]

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "abcabc"
Output:
10
Explanation:
10 substrings hold all of a, b and c.

Example 2

Input:
s = "aaacb"
Output:
3
Explanation:
3 valid substrings.

Example 3

Input:
s = "abc"
Output:
1
Explanation:
Only "abc" itself works → 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.