Sliding Window: Given a string, get the number of substrings having ‘a’, ‘b’, ‘c’

Problem Statement:

Given a string, get the number of substrings having ‘a’, ‘b’, ‘c’

Example:

Input: str = "abcabc"

Output: 10

Solution Explanation:

We can solve this problem by using sliding window technique.

Take 2 pointers left and right.
Take a map, to store the frequency of a, b, c.

Keep increasing the right window and when the value of a, b, c becomes greater than one, increment the result.

Then shrink the window and continue the process.

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

Code Solution

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


int solution(string s) 
{
    int n = s.size();

    int left = 0;
    int right = 0;
    int count = 0;

    unordered_map<char, int> mp;

    while(right<n)
    {
        mp[s[right]]++;

        while(mp['a']>=1 && mp['b']>=1 && mp['c']>=1)
        {
            count += (n - right);

            mp[s[left]]--;
            left++;
        }
        right++;
    }
    
    return count;
}

int main() 
{
    string str = "abcabc";

    cout << solution(str);
}

Output
————-

10