Number of Substrings Containing All Three Characters

Number of Substrings Containing All Three Characters - Problem

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcabc"

› Output: 10

💡 Note: Substrings containing all three: "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc", "abc" (from position 3-5)

Example 2 — Minimum Valid

$ Input: s = "aaacb"

› Output: 3

💡 Note: After seeing all three chars at position 4, substrings "aaacb", "aacb", "acb" contain a, b, and c

Example 3 — No Valid Substrings

$ Input: s = "abc"

› Output: 1

💡 Note: Only one substring "abc" contains all three characters

Constraints

3 ≤ s.length ≤ 5 × 10⁴
s only consists of 'a', 'b' or 'c' characters.

Visualization

Tap to expand

Understanding the Visualization

Input

String s with only characters a, b, c

Process

Find substrings containing all three characters

Output

Count of valid substrings

Key Takeaway

🎯 Key Insight: Once we find all three characters, every extension creates more valid substrings

Asked in

a Amazon 15 M Microsoft 8

The key insight is to track the last positions of characters 'a', 'b', and 'c'. Once all three characters are seen, we can count valid substrings efficiently. Best approach is sliding window with Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window Optimization	O(n)	O(1)	Use sliding window to track last positions of a, b, c and count valid substrings efficiently
Brute Force - Check All Substrings	O(n³)	O(1)	Check every possible substring to see if it contains all three characters

Sliding Window Optimization — Algorithm Steps

Track last positions of a, b, c
For each character, find the earliest position where all three exist
Count substrings from start to that position

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Positions

Keep track of last seen positions of a, b, c

Find Earliest

Find the earliest position where all three exist

Count Substrings

Count valid substrings ending at current position

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int min(int a, int b, int c) {
    int result = a;
    if (b < result) result = b;
    if (c < result) result = c;
    return result;
}

int solution(char* s) {
    int n = strlen(s);
    int count = 0;
    int lastA = -1, lastB = -1, lastC = -1;
    
    for (int i = 0; i < n; i++) {
        if (s[i] == 'a') {
            lastA = i;
        } else if (s[i] == 'b') {
            lastB = i;
        } else if (s[i] == 'c') {
            lastC = i;
        }
        
        // If we have seen all three characters
        if (lastA != -1 && lastB != -1 && lastC != -1) {
            // The earliest position where all three exist
            int earliest = min(lastA, lastB, lastC);
            // All substrings from 0 to earliest that end at i are valid
            count += earliest + 1;
        }
    }
    
    return count;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, constant work per character

✓ Linear Growth

Space Complexity

O(1)

Only storing three position variables

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler