Skip to main content

Number of substring containing all three characters

Problem Statement:​

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.

  • Example:

    Example 1:

    Input: s = "abcabc"
    Output: 10
    Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again). 
    Example 2:

    Input: s = "aaacb"
    Output: 3
    Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb". 
    Example 3:

    Input: s = "abc"
    Output: 1

Solution:​

int numberOfSubstrings(string s) {
    int hash[3] = {-1, -1, -1}; // stores last index of 'a', 'b', and 'c'
    int count = 0;

    for (int i = 0; i < s.size(); i++) {
        hash[s[i] - 'a'] = i; // update last seen index of current char

        // add number of substrings ending at i that contain all three letters
        count += (1 + min({hash[0], hash[1], hash[2]}));
    }

    return count;
}

🧠 How it Works​

  • For each character, store its last seen index.
  • When all three letters have appeared at least once, the smallest last index determines the earliest valid start.
  • Number of valid substrings ending at i = 1 + min(last_seen_a, b, c)

⚠️ Edge Cases​

  • String with fewer than 3 characters → returns 0
  • Works only with 'a', 'b', and 'c' → extendable by using a map or array of size 26

📉 Time & Space Complexity​

MetricValue
TimeO(n)
SpaceO(1) — array of size 3

💡 Other Possible Solutions​

  • Sliding Window + Count Map: Maintain window with all three characters → expand and shrink → O(n)
  • Brute Force: Generate all substrings and check → O(n²)

🔁 Related Problems​

  • LC 1358 – Number of Substrings Containing All Three Characters
  • Minimum Window Substring (LC 76)
  • Longest substring with at most K distinct characters

📚 Concepts Used​

  • Index tracking
  • Minimum of last seen positions
  • Substring counting from end position
💬

Discussion & Doubts