Simple C++ Approach and Solution | Weekly Contest 420 | Question 2
Intuition\n Describe your first thoughts on how to solve this problem. \n1. Fix the left index of the substring.\n2. For the fixed left index, find the first ri
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. Fix the left index of the substring.\n2. For the fixed left index, find the first right index for which substring `s[left..right]` satisfies the condition.\n3. Every substring that starts at left and ends after right satisfies the condition.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. if `k == 1`, then all substrings are valid because every character appears at least once.\n2. if `k >=2`, then we try to check all the substring using sliding window concept.\n3. iterate the loop from left to end of string.\n4. we increment the frequency of character during iterating the string. `mp[s[right]]++;`.\n5. we check the condition `if(mp[s[right]] == k)` whether it satisfy or not.\n6. if it satisfy then every substring that starts at left and ends after right satisfies the condition.\n7. at last, return `count`.\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int numberOfSubstrings(string s, int k) {\n        \n        int count = 0;\n        int n = s.length();\n        if(k == 1) return n*(n+1)/2;\n        for(int left = 0; left < n; left++){\n            unordered_map<char, int> mp;\n            for(int right = left; right < n; right++){\n                mp[s[right]]++;\n                if(mp[s[right]] == k){\n                    count += (n - right);\n                    break;\n                }\n            }\n        }\n        return count;\n    }\n};\n```
['Hash Table', 'String', 'Sliding Window', 'C++']