Number of Substrings Containing All Three Characters - Sliding Window - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given a string s consisting only of the characters 'a', 'b', and 'c', your task is to count the number of non-empty substrings that contain at least one occurrence of each character.

Example:

  • Input: s = "abcabc"
  • Output: 10

All valid substrings: "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc", "abc"

Examples❯

Input (s) Output Description
"abcabc" 10 All valid substrings that contain 'a', 'b', and 'c'. Total: 10 substrings such as "abc", "bca", "cab", etc.
"aaabcb" 3 Only three substrings like "aabcb", "abcb", and "bcb" contain all three characters 'a', 'b', and 'c'.
"aaaa" 0 No valid substrings — only character 'a' is present, so no substring can contain all 'a', 'b', and 'c'.
"abc" 1 Only one valid substring — the whole string itself contains all 'a', 'b', and 'c'.
"aabbcc" 4 Valid substrings like "abbc", "abbcc", "bbcc", and "aabbcc" include all three characters.
"cba" 1 One valid substring — the entire string "cba" contains 'a', 'b', and 'c'.
"cababac" 11 Sliding window identifies multiple valid substrings containing all three characters.
"ab" 0 Only two characters are present — cannot form a valid substring with all three characters.
"a" 0 Only one character — no way to get all three characters in any substring.
"" 0 Empty input — no substrings at all, hence result is 0.

Solution❯

Understanding the Problem

We are given a string s that only contains the characters 'a', 'b', and 'c'. Our task is to count the number of non-empty substrings of s that contain at least one occurrence of each of the three characters.

In simpler terms, we want to find all possible substrings that have all three characters — 'a', 'b', and 'c' — at least once, no matter their order.

Step-by-Step Solution with Example

Step 1: Take the example s = "abcabc"

We will use a two-pointer sliding window approach to move through the string and maintain a window that always tries to include all three characters. The goal is to count how many substrings end at each position that contain all three characters.

Step 2: Initialize pointers and tracking structures

  • Start with two pointers: left = 0 and right that moves from 0 to end of string.
  • Use a dictionary count to keep track of how many 'a', 'b', and 'c' are in the current window.
  • Initialize total = 0 to store the count of valid substrings.

Step 3: Move the right pointer and update the count

As right increases, we add s[right] to our count map. This helps us know how many of each character are in the current window.

Step 4: Check if window is valid

Each time the window contains at least one of 'a', 'b', and 'c', we know it is a valid window. From here, we can say all substrings that start at left and end anywhere from right to the end of the string are valid.

So, we add (length - right) to total.

Step 5: Shrink the window from the left

We then reduce the window from the left side by removing s[left] from the count and moving left forward. This helps us find the next possible smaller window that still contains all three characters.

Step 6: Repeat until right reaches the end

Continue the above process until right has scanned the entire string. At each step, we keep updating our total count.

Final Result for s = "abcabc"

The total valid substrings that contain all three characters are 10. Some examples include: "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc", "abc".

Edge Cases

  • Short Strings: If the string has less than 3 characters, it’s impossible to contain all three characters. Return 0.
  • Missing Character: If any one of 'a', 'b', or 'c' is not present in the string at all, return 0.
  • Repeated Characters: If string is something like "aaabbbccc", it may take longer for a valid window to form, but the logic still holds.
  • All characters same: For example, "aaaa" → No substring will contain all three characters. Return 0.

Final Thoughts

This problem is a great example of how sliding window and two pointer techniques help avoid brute force approaches. Instead of checking all substrings explicitly (which would take O(n²) time), we only scan the string once and use a smart window adjustment strategy to compute the answer in linear time.

As a beginner, focus on understanding how the left and right pointers move and how the count map helps us decide whether a window is valid.

Algorithm Steps❯

  1. Initialize a hash map or frequency counter count to track occurrences of 'a', 'b', and 'c'.
  2. Use two pointers: left starting at index 0 and right iterating through the string.
  3. Initialize total = 0 to keep track of the valid substrings.
  4. As right moves forward, increment the count of s[right].
  5. While all three characters are present in the current window (i.e., all counts are ≥ 1):
  6. → Add (length - right) to total, because all substrings starting at left and ending from right to end are valid.
  7. → Shrink the window from the left by decrementing the count of s[left] and incrementing left.
  8. Repeat until right reaches the end of the string.
  9. Return total as the result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>

int countSubstrings(char* s) {
    int count[3] = {0, 0, 0};
    int left = 0, total = 0, n = strlen(s);
    int unique = 0;

    for (int right = 0; right < n; right++) {
        count[s[right] - 'a']++;
        if (count[s[right] - 'a'] == 1) unique++;

        while (unique == 3) {
            total += n - right;
            count[s[left] - 'a']--;
            if (count[s[left] - 'a'] == 0) unique--;
            left++;
        }
    }
    return total;
}

int main() {
    char s[] = "abcabc";
    int result = countSubstrings(s);
    printf("%d\n", result); // 10
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, the sliding window still needs to examine each character at least once with the right pointer and may increment the left pointer as well. Since each character is processed at most twice (once by right, once by left), the time complexity remains linear.
Average CaseO(n)Both pointers (left and right) traverse the string once. For every character added by the right pointer, the left pointer may be moved forward to maintain the window. So, the number of total operations is proportional to the length of the string.
Worst CaseO(n)Even in the worst case, each character is visited a constant number of times (once by the right pointer and at most once by the left), resulting in O(n) total time complexity.

Space Complexity❯

O(1)

Explanation: Only a fixed amount of extra space is used — a frequency counter (with three entries for 'a', 'b', and 'c') and a few variables like total, left, and right. Space usage does not scale with input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...