C++/Java/Python/JavaScript | 🚀 ✅ Sliding Window | 🚀✅ Hash Table
Intuition:\n- The problem requires us to find the number of substrings in a given string s that contain all the characters \'a\', \'b\', and \'c\'. To solve thi
# Intuition:\n- The problem requires us to find the number of substrings in a given string s that contain all the characters \'a\', \'b\', and \'c\'. To solve this, we can use a sliding window approach where we maintain two pointers, start and end, and an unordered map to keep track of the count of each character in the current window. We keep expanding the window by moving the end pointer until we find a window that contains all three characters. Once we find such a window, we know that all the substrings starting from the start pointer up to the end pointer will contain all three characters. We can add the count of such substrings to our answer and move the start pointer to the right until we no longer have a valid window. We repeat this process until we reach the end of the string.\n\n# Approach:\n\n1. Initialize an unordered map to keep track of the count of each character in the current window, count variable to store the number of valid substrings, start and end pointers, and the length of the string n.\n2. Move the end pointer to the right until we find a window that contains all three characters \'a\', \'b\', and \'c\'. For this, we can use a while loop that checks if the count of each character in the map is greater than zero.\n3. Once we find a valid window, we know that all the substrings starting from the start pointer up to the end pointer will contain all three characters. We can add the count of such substrings to our answer by adding n - end to the count variable. This is because we can form n - end substrings from the current end pointer to the end of the string.\n4. Move the start pointer to the right until we no longer have a valid window. We do this by decrementing the count of the character at the start pointer in the map and moving the start pointer to the right until we no longer have all three characters in the window.\n5. Repeat steps 2 to 4 until we reach the end of the string.\n6. Return the count variable.\n# Complexity:\n- Time complexity: O(n) where n is the length of the string. We visit each character of the string at most twice, once by the end pointer and once by the start pointer.\n- Space complexity: O(1) since the size of the unordered map is constant at 3 (for the characters \'a\', \'b\', and \'c\').\n\n# C++\n```\nclass Solution {\npublic:\n    int numberOfSubstrings(string s) {\n        unordered_map<char,int> map;\n        int count = 0, start = 0, end = 0;\n        int n = s.size();\n        while(end<n){\n            map[s[end]]++;\n            while( map[\'a\'] && map[\'b\'] && map[\'c\'] ){\n                count+=n-end;\n                map[s[start]]--;\n                start++;\n            }\n            end++;\n        }\n        return count;\n    }\n};\n```\n# JavaScript\n```\nvar numberOfSubstrings = function (s) {\n  const map = {};\n  let count = 0, start = 0, end = 0;\n  const n = s.length;\n  while (end < n) {\n    map[s[end]] = (map[s[end]] || 0) + 1;\n    while (map[\'a\'] && map[\'b\'] && map[\'c\']) {\n      count += n - end;\n      map[s[start]]--;\n      start++;\n    }\n    end++;\n  }\n  return count;\n}\n\n```\n# Java\n```\nclass Solution {\n    public int numberOfSubstrings(String s) {\n        Map<Character, Integer> map = new HashMap<>();\n        int count = 0, start = 0, end = 0;\n        int n = s.length();\n        while (end < n) {\n            char c = s.charAt(end);\n            map.put(c, map.getOrDefault(c, 0) + 1);\n            while (map.getOrDefault(\'a\', 0) > 0\n                    && map.getOrDefault(\'b\', 0) > 0\n                    && map.getOrDefault(\'c\', 0) > 0) {\n                count += n - end;\n                c = s.charAt(start);\n                map.put(c, map.get(c) - 1);\n                start++;\n            }\n            end++;\n        }\n        return count;\n    }\n}\n\n```\n# Python\n```\ndef numberOfSubstrings(s):\n    map = {}\n    count = 0\n    start = end = 0\n    n = len(s)\n    while end < n:\n        map[s[end]] = map.get(s[end], 0) + 1\n        while map.get(\'a\', 0) > 0 and map.get(\'b\', 0) > 0 and map.get(\'c\', 0) > 0:\n            count += n - end\n            map[s[start]] -= 1\n            start += 1\n        end += 1\n    return count\n\n```\n\n#### Thank You
['Hash Table', 'Sliding Window', 'Python', 'C++', 'Java']