Count Substrings Containing All Three Characters

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"

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.

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.

#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;
}

#include <iostream>
#include <string>
using namespace std;

int countSubstrings(const string& s) {
    int count[3] = {0, 0, 0};
    int left = 0, total = 0, unique = 0;
    int n = s.length();

    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() {
    string s = "abcabc";
    cout << countSubstrings(s) << endl; // 10
    return 0;
}

def count_substrings(s: str) -> int:
    count = {'a': 0, 'b': 0, 'c': 0}
    left = 0
    total = 0
    unique = 0
    n = len(s)

    for right in range(n):
        count[s[right]] += 1
        if count[s[right]] == 1:
            unique += 1

        while unique == 3:
            total += n - right
            count[s[left]] -= 1
            if count[s[left]] == 0:
                unique -= 1
            left += 1

    return total

# Example usage
s = "abcabc"
print(count_substrings(s))  # 10

public class SubstringCounter {
    public static int countSubstrings(String s) {
        int[] count = new int[3];
        int left = 0, total = 0, unique = 0;
        int n = s.length();

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

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

    public static void main(String[] args) {
        String s = "abcabc";
        System.out.println(countSubstrings(s)); // 10
    }
}

function countSubstrings(s) {
  const count = { a: 0, b: 0, c: 0 };
  let left = 0, total = 0, unique = 0;
  const n = s.length;

  for (let right = 0; right < n; right++) {
    count[s[right]]++;
    if (count[s[right]] === 1) unique++;

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

// Example usage
const s = "abcabc";
console.log(countSubstrings(s)); // 10

package main

import "fmt"

func countSubstrings(s string) int {
    count := [3]int{0, 0, 0}
    left, total, unique := 0, 0, 0
    n := len(s)

    for right := 0; right < n; right++ {
        idx := s[right] - 'a'
        count[idx]++
        if count[idx] == 1 {
            unique++
        }

        for unique == 3 {
            total += n - right
            leftIdx := s[left] - 'a'
            count[leftIdx]--
            if count[leftIdx] == 0 {
                unique--
            }
            left++
        }
    }
    return total
}

func main() {
    s := "abcabc"
    fmt.Println(countSubstrings(s)) // 10
}

fn count_substrings(s: &str) -> i32 {
    let mut count = [0; 3];
    let (mut left, mut total, mut unique) = (0, 0, 0);
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();

    for right in 0..n {
        let idx = (chars[right] as u8 - b'a') as usize;
        count[idx] += 1;
        if count[idx] == 1 {
            unique += 1;
        }

        while unique == 3 {
            total += (n - right) as i32;
            let left_idx = (chars[left] as u8 - b'a') as usize;
            count[left_idx] -= 1;
            if count[left_idx] == 0 {
                unique -= 1;
            }
            left += 1;
        }
    }
    total
}

fn main() {
    let s = "abcabc";
    println!("{}", count_substrings(s)); // 10
}

fun countSubstrings(s: String): Int {
    val count = IntArray(3) { 0 }
    var left = 0
    var total = 0
    var unique = 0
    val n = s.length

    for (right in 0 until n) {
        val idx = s[right] - 'a'
        count[idx]++
        if (count[idx] == 1) unique++

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

fun main() {
    val s = "abcabc"
    println(countSubstrings(s)) // 10
}

func countSubstrings(_ s: String) -> Int {
    var count = [0, 0, 0]
    var left = s.startIndex
    var total = 0
    var unique = 0
    let n = s.count

    var right = s.startIndex
    while right < s.endIndex {
        let idx = Int(s[right].asciiValue! - Character("a").asciiValue!)
        count[idx] += 1
        if count[idx] == 1 {
            unique += 1
        }

        while unique == 3 {
            total += n - s.distance(from: s.startIndex, to: right)
            let leftIdx = Int(s[left].asciiValue! - Character("a").asciiValue!)
            count[leftIdx] -= 1
            if count[leftIdx] == 0 {
                unique -= 1
            }
            left = s.index(after: left)
        }
        right = s.index(after: right)
    }

    return total
}

let s = "abcabc"
print(countSubstrings(s)) // 10

function countSubstrings(s: string): number {
  const count: { [key: string]: number } = { a: 0, b: 0, c: 0 };
  let left = 0, total = 0, unique = 0;
  const n = s.length;

  for (let right = 0; right < n; right++) {
    count[s[right]] = (count[s[right]] || 0) + 1;
    if (count[s[right]] === 1) unique++;

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

// Example usage
const s = "abcabc";
console.log(countSubstrings(s)); // 10

Time complexity

Space complexity

O(1)

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.