Number of Substrings Containing All Three Characters in C++

Suppose we have given a string s consisting only of characters a, b and c. We have to return the number of substrings containing at least one occurrence of all these characters a, b and c. So for example, if the string is “abcabc”, then the output will be 10, as the substring containing at least one occurrence of the characters a, b and c, these are “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “cab”, “cabc” and “abc” (again for the last part).

To solve this, we will follow these steps −

• ret := 0, make a map called m, set j := 0

• for i in range 0 to size of s

  • increase count of s[i] in the map m

  • while m[‘a’] > 0 and m[‘b’] > 0 and m[‘c’] > 0,

    • decrease the count of s[i] in map m

    • increase j by 1

  • increase ret by j

• return ret

Example (C++)

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    int numberOfSubstrings(string s) {       int ret = 0;       map <char, int> m;       int j = 0;       for(int i = 0; i < s.size(); i++){          m[s[i]]++;          while(m['a'] > 0 && m['b'] > 0 && m['c'] > 0){             m[s[j]]--;             j++;          }          ret += j;       }       return ret;    } }; main(){    Solution ob;    cout << (ob.numberOfSubstrings("abcabc")); }

Input

"abcabc"

Output

10