Problem Statement

Given a string s , consisting only of characters 'a' , 'b' , 'c'.Find the number of substrings that contain at least one occurrence of all these characters 'a' , 'b' , 'c'.

Examples

Example 1:

Input: s = "abcabc"
Output: 10

Explanation:
The substrings that contain at least one occurrence of a, b, c are:
"abc"
"abca"
"abcab"
"abcabc"
"bca"
"bcab"
"bcabc"
"cab"
"cabc"
"abc"

Example 2:

Input: s = "aaacb"
Output: 3

Explanation:
The substrings that contain at least one occurrence of a, b, c are:
"acb"
"aacb"
"aaacb"

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Generate all possible substrings and check if each contains 'a', 'b', and 'c'. Though simple, it’s inefficient due to the high computational cost.

Approach:

1. Generate all substrings using two nested loops.
2. For each substring, check if it contains 'a', 'b', and 'c'.
3. Increment a counter for valid substrings.

Code:

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

int countSubstrings(string s) {
    int n = s.size();
    int count = 0;

    for (int i = 0; i < n; i++) {
        bool hasA = false, hasB = false, hasC = false;
        for (int j = i; j < n; j++) {
            if (s[j] == 'a') hasA = true;
            if (s[j] == 'b') hasB = true;
            if (s[j] == 'c') hasC = true;
            if (hasA && hasB && hasC) count++;
        }
    }
    return count;
}

int main() {
    string s = "abcabc";
    cout << countSubstrings(s) << endl; // Output: 10
    return 0;
}

OR:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the number of substrings 
    containing all characters 'a', 'b', 'c' in string s. */
    int numberOfSubstrings(string s) {
        int count = 0;
        
        // Iterate through each starting point of substring
        for (int i = 0; i < s.size(); ++i) {
            
            // Array to track presence of 'a', 'b', 'c'
            int hash[3] = {0}; 
            
            // Iterate through each ending point of substring
            for (int j = i; j < s.size(); ++j) {
                
                // Mark current character in hash
                hash[s[j] - 'a'] = 1; 
                
                /* Check if all characters
                'a', 'b', 'c' are present*/
                if (hash[0] + hash[1] + hash[2] == 3) {
                    
                    // Increment count for valid substring
                    count++; 
                }
            }
        }
        // Return the total count of substrings
        return count;
    }
};

int main() {
    string s = "bbacba";

    // Create an instance of Solution class
    Solution sol;
    
    int ans = sol.numberOfSubstrings(s);

    // Print the result
    cout << "Number of substrings containing 'a', 'b', 'c' in \"" << s << "\" is: " << ans << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2), where N is the size of the string. The outer loop runs for N time and for each character the inner loop also runs for N times.
• Space Complexity: O(1) . As no significant amount of extra space is used.

2️⃣ Optimal Approach

Intuition:

Instead of maintaining a frequency array, track the most recent positions of 'a', 'b', and 'c'. Use the minimum of these indices to calculate valid substrings.

Approach:

1. Maintain variables to store the last seen positions of 'a', 'b', and 'c'.
2. For each character, update its last seen position.
3. Calculate the number of valid substrings starting at the minimum of the three positions.

Dry Run:

Code:

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

int countSubstrings(string s) {
    int n = s.size();
    int lastA = -1, lastB = -1, lastC = -1, count = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == 'a') lastA = i;
        if (s[i] == 'b') lastB = i;
        if (s[i] == 'c') lastC = i;

        int minIndex = min({lastA, lastB, lastC});
        if (minIndex != -1) {
            count += minIndex + 1;
        }
    }
    return count;
}

int main() {
    string s = "abcabc";
    cout << countSubstrings(s) << endl; // Output: 10
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)