Variable window size Sliding window technique O(n) solution with explanation for Interviews
I have tried to provide the explanation the way you can answer in interviews.\nStep by step, try to give your thoughts before you provide your optimised code, t
***I have tried to provide the explanation the way you can answer in interviews.\nStep by step, try to give your thoughts before you provide your optimised code, this way, you will defintely get the role!!***\n### Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- This problem is similar to ques:\'longest substring with K unique characters\', difference is we will keep count of such subtsrings and not find the maximum.\n- brute force approach will be to use two loops, to traverse the window and check the number of characters and keep the count (O(n^2)). Using sliding window will optimise it by reducing the repetitive work. \n\n### Approach\n<!-- Describe your approach to solving the problem. -->\n- we will use two pointers i and j for a window and we will keep traversing j, until we get the required window size.\n- The required window size will be when the window substring will fulfill the condition of having 3 unique chars. Using a hashmap to keep count of chars in the window. \n- to avoid using two loops, we will keep on pushing chars to map while traversing j to reach the reqd window.\n- Since whole string will always have 3 unique chars(a,b and c), we will get candidates of answer when the window will have 3 unique chars, ie when map size will be equal to 3. \n- when we get the required window, we can calculate count and secondly, traverse i too. As we traverse i, we need to also remove the calculations of i from the map. \n- the calculation of count can be given by (1+ end-j), which is calculated as we count all substrings from the jth point to the end of substring having the same i.(this hack will reduce TC). eg: in given example 1 of problem, if "abc" is the window, "abc", "abca", "abcab", "abcabc" is given by the above count formula. \n\n Time complexity: O(n) \n Space complexity: O(1), since map size will always be 3 \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n\n# Code\n```\nclass Solution {\npublic:\n\n    int numberOfSubstrings(string s) {\n        \n    unordered_map<char,int> mp;  \n    int count=0;\n    int i=0; int j=0;\n    inteint end=s.size()-1;\n\n    while(j<s.size()){\n        //calculations while travsering j \n        mp[s[j]]++;\n\n        //when window size is less than reqd\n        if(mp.size()<3){\n            //we need to traverse j \n            j++;\n        }\n        else if(mp.size()==3){\n            //once it reached, we save the count and shrink the window size from left \n            // till the time, we have 3 distinct chars, we can go on calculating count and increase i but not increasing j\n            //eg input \'aaacb\' \n            while(mp.size()==3){\n                count+=1+end-j;\n                mp[s[i]]--;\n            if(mp[s[i]]==0){\n                mp.erase(s[i]);\n            }\n            i++;\n            }\n            j++;\n        }\n    } return count;\n    }\n};\n\n```\nPlease upvote if you like!\n\n\n
['Hash Table', 'Sliding Window', 'C++']