[C++] || O(n) || WITH explaination
Let\u2019s say we have an example string : \u2018abcabc\u2019.\n\n\n\n\n- Therefore the substrings that fulfills the given condition are :\n- Each substring has
- Let\u2019s say we have an example string : \u2018abcabc\u2019.\n![image](https://assets.leetcode.com/users/images/5659f1f2-8c2a-4343-b1e8-a7711a0d7ddd_1661665420.1759043.png)\n\n\n\n- Therefore the substrings that fulfills the given condition are :\n- Each substring has atleast one occurrence, each of \u2018a\u2019 , \u2018b\u2019 and \u2018c\u2019.\n\n![image](https://assets.leetcode.com/users/images/60b97545-6ddb-4359-9119-d86e81dc339a_1661665470.9467251.png)\n\n![image](https://assets.leetcode.com/users/images/2b9dc914-52f9-4b66-b0ac-d07d14c57629_1661665471.2515423.png)\n\n### How to use sliding window:\n\n- We will use two pointers, namely , \u2018l\u2019 and \u2018r\u2019, which will form a \u2018window\u2019 to fulfill a condition.\n- Basically, we need a \u2018window\u2019 , of atleast size 3, which will have atleast one occurrence of \u2018a\u2019 , \u2018b\u2019 and \u2018c\u2019.\n\n```\n\tso a \'window\' should fulfill 1 condition atleast to call it the substring we need :\n\t\n    * \'a\' , \'b\' and \'c\' should have occurred atleast once \n\t\t\n```\n\n- Both \u2018l\u2019 and \u2018r\u2019 are intialized with 0.\n- We will move \u2018r\u2019 forward, while \u2018l\u2019 will move forward when \u2018window\u2019 condition is fulfilled.\n- At r = 0 , we have \u2018a\u2019 (ie at \u2018r\u2019th index). We store \u2018a\u2019 and its frequency in a map.\n- As we insert \u2018a\u2019 and its frequency (ie 1), map size = 1\n- We increment \u2018r\u2019 forward as \u2018window\u2019 condition is not fulfilled yet.\n\n![image](https://assets.leetcode.com/users/images/158bda8c-8a87-453a-b3b6-162df96d3b24_1661665574.2769723.png)\n\n- Now, r = 1 , \u2018b\u2019 is at \u2018r\u2019th index. As \u2018b\u2019 has been encountered for the first time, we store \u2018b\u2019 and its frequency (ie 1) , we store it in our map.\n- As a result, our map size increases 2.\n- We increment \u2018r\u2019 as \u2018window\u2019 condition is not fulfilled yet.\n\n![image](https://assets.leetcode.com/users/images/244624fc-84e9-48f6-b7b6-1c02eaf7104f_1661665604.9635782.png)\n\n- Now , r = 3, we encounter \u2018c\u2019 at \u2018r\u2019th index. As it has occurred for the first time, we store \u2018c\u2019 and its frequency (ie 1) in map.\n- Notice now, that our \u2018window\u2019 condition is fulfilled ie the map contains \u2018a\u2019 , \u2018b\u2019 and \u2018c\u2019!!\n- Therefore we have found a substring, which ranges from index \u2018l\u2019 to index \u2018r\u2019, which fulfills the condition.\n\n![image](https://assets.leetcode.com/users/images/6a52efd3-7205-45d9-a7c0-9e414ce69f4b_1661665644.5019782.png)\n\n- Now, for this \u2018window\u2019 which already fulfills the condition, even if I add more characters from the \u2018end\u2019 tail, ie after \u2018r\u2019th index, they would also count as valid substrings that fulfill the condition.\n- For example , from \u2018l\u2019 to \u2018r\u2019 we have substring as \u2018abc\u2019. Now, after \u2018r\u2019th index we have \u2018a\u2019. If we add this to the existing \u2018window\u2019 ie \u2018abc\u2019 , then it becomes \u2018abca\u2019, which is a valid substring which fulfills the condition that all \u2018a\u2019 , \u2018b\u2019 and \u2018c\u2019 occurred atleast once. Similarly if I add \u2018ab\u2019 to the window ie \u2018abcab\u2019, this is also a valid substrings.\n\n```\n\n  \tSo basically the moment our \'window\' condition is fufilled, all characters after \n\t\t\'r\'th index can also be added to this \'window\' to count them as valid substrings\n\n```\n\n![image](https://assets.leetcode.com/users/images/590625b6-3888-43ce-9fb4-7eff6c023854_1661665705.9298844.png)\n\n- To count all those valid substrings, we can count it by finding the number of characters after \u2018r\u2019 by subtracting it with the length of string (here \u2018len\u2019).\n- We add \u2018+1\u2019 to count the existing \u2018window\u2019 also as valid substring.\n\n![image](https://assets.leetcode.com/users/images/521d6ab9-8309-43c5-b74c-fd0ba71185ea_1661665739.5084302.png)\n\n- Now, since we have counted all the valid substrings of this \u2018window\u2019 , we go to the next window, by incrementing \u2018l\u2019 as well as \u2018r\u2019.\n- But, before, we increment \u2018l\u2019, we have to remove the frequency of character at \u2018l\u2019th index, as we are transitioning into the next \u2018window\u2019.  Therefore reduce the frequency of the the character at \u2018l\u2019th character from map.\n- Now, repeat this for every \u2018window\u2019 as \u2018r\u2019 moves forward upto the length of the string.\n\n![image](https://assets.leetcode.com/users/images/7ac3a5f6-b2f0-4f44-8018-b87361a0a510_1661665783.8019476.png)\n\n\n### Code (C++)\n\n```\nclass Solution \n{\n public :\n  int numberOfSubstrings(string s) \n  {\n    int l = 0 , r = 0 ;\n    //two pointers \'l\' and \'r\' respectively\n    \n    map<char,int>mp;\n    //map \n\n    int len = s.size() - 1;\n    \n    int cnt = 0; //to store answer\n\n    while(r!=s.size()) //while \'r\' reaches the last index\n    {\n        mp[s[r]]+=1; //count frequency of each character for each \'r\' index\n\n        while(mp[\'a\'] and mp[\'b\'] and mp[\'c\']) // when an index \'l\' and \'r\' has come such that \'a\',\'b\',\'c\' all 3 exists in map\n        {\n            cnt+=1 + (len-r); // count all substrings that can be formed till \'r\'\n            \n            mp[s[l]]-=1; //shrink window size by reducing the frequency of \'lth\' character\n            \n            l++; //increment \'l\' to go to next window\n        }\n        r++; //increment \'r\' \n    }\n\n    return cnt;\n  }\n};\n \n```
['Hash Table', 'Two Pointers', 'String', 'Sliding Window', 'C++']