What is the brute force approach and complexity for Number of Substrings Containing All Three Characters?

For each start, grow until all three letters appear, then add n − end with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Number of Substrings Containing All Three Characters?

While the window has a, b, c, add n − right and shrink from the left with optimal time complexity O(N) and space complexity O(1).

Number of Substrings Containing All Three Characters

Q: How do you identify the pattern for Number of Substrings Containing All Three Characters?

Look for key signals in the prompt: "number of substrings" indicates Counting problem → add a block of substrings per step, not 1 at a time.; "at least one a, b and c" indicates An "at least" rule. Growing keeps it true, so once a window is good, all its right-extensions are good.; "only a, b, c" indicates The complement "missing a letter" is the same as "at most 2 distinct", which makes the total − at-most trick possible. Three counters are enough state..

Medium·LeetCode #1358 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given a string s made only of the letters a, b and c.

Count how many substrings contain at least one a, at least one b and at least one c.

Input

A string s containing only the characters a, b, c.

Output

The number of substrings that contain all three letters.

Example 1

Input: s = "abcabc"

Output: 10

The good substrings are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (the last one starting at index 3).

Example 2

Input: s = "aaacb"

Output: 3

The good substrings are "aaacb", "aacb" and "acb".

Example 3

Input: s = "abc"

Output: 1

Only the whole string has all three letters.

Constraints

• 3 ≤ s.length ≤ 5·10^4
• s contains only 'a', 'b' and 'c'.
• The answer is at most n(n+1)/2 ≈ 1.25·10^9, which still fits in an int, but n·(n+1) does not.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“number of substrings”

→ Counting problem → add a block of substrings per step, not 1 at a time.

“at least one a, b and c”

→ An "at least" rule. Growing keeps it true, so once a window is good, all its right-extensions are good.

“only a, b, c”

→ The complement "missing a letter" is the same as "at most 2 distinct", which makes the total − at-most trick possible. Three counters are enough state.

Approach Complexity Ladder

Brute Force — first good end for every startO(N²)O(1)

For each start, grow until all three letters appear, then add n − end

Better — count the complement (at most 2 distinct)O(N)O(1)

All substrings minus the ones with at most 2 distinct letters

Optimal — at-least window, add n − rightO(N)O(1)

While the window has a, b, c, add n − right and shrink from the left

Brute Force Intuition

Fix a start. Grow the end and count letters. The first time all three letters are present, every longer substring from this start is also good, so add n − end and move to the next start.

Recognition rule for this sub-pattern:

Count subarrays that satisfy a rule. "At most": for each right end, every start from left to right works, so add (right − left + 1). "At least": once the window is good, every longer one is too, so add left (or n − right).

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Subarray Product Less Than K Count Subarrays Where Max Element Appears at Least K Times