C++ sliding window - hints - intuition explained - commented code
to move directly to the approach first make sure you have tried these questions:\n\t maximum consecutive ones iii\n\t longest substring with at most k distinct 
* to move directly to the approach first **make sure you have tried these questions**:\n\t* [maximum consecutive ones iii](https://leetcode.com/problems/max-consecutive-ones-iii/)\n\t* longest substring with at most k distinct characters\n* rather then moving to approach of this problem, we will **first see the approach to the problem mentioned above [longest substring with at most k distinct characters]** using sliding window\n\t* Now,**when we add an element, there could be 2 cases:**\n\t\t\t**1**. \t**element is distinct**: we have found one of the distinct element so we will decrease k as now only k-1 disitnct elements can be added furthur - **[k--]**\n\t\t\t**2**. \t**element is not distinct**: no issues! as that is not going to affect k as similar element is already seen before, so we just need to increase its frequency and that\'s it! \uD83D\uDE04 -  [**nothing specific to be done!]**\n\t* for above 2 cases, to check whether element is distinct or not, we need to have a **data structure which can store frequency of every element and can access it in minimal time**. And we know that this data structure is **our dearest unordered Map** \uD83D\uDC99. So we will declare and unordered map and will be updating the frequency of elements in it in every iteration.\n\t* Now, **we will keep moving until we reach the danger** \uD83D\uDC80\u26A1 **point - when k < 0** that means **we have colllected the maximum limit of distinct characters and we have one extra distinct character** and now k is exhausted. Now, this extra distinct character is evil\uD83D\uDE08 so we need to remove it as we want to make k = 0 to satisfy the given conditions.\n\t* Now, to make k back to safe. So for the same we we will use **2 pointer approach** position ie., 0. we need to go to starting and minimize the window unitl we get k=0. We will decrease the start pointer until we reach a positions where k becomes zero again.\n\t* So after all these long points \uD83E\uDD74, let me summarize the conditions:\n\t\t\t**1. k > 0: no issues. Just update the length and update frequency.**\n\t\t\t**2. k = 0: danger point. but nothing specific to do. all operations like k>0 to be performed.**\n\t\t\t**3. k < 0: unstable condition. immediately have to make k = 0 by 2 pointer approach. Decrementing k until getting k back to 0 and updating freq in map along with.**\n#### \t\t\t***CODE FOR LONGEST SUBSTRING WITH AT MOST K DISTINCT CHARACTERS***\n```\n\nstring longestSubstringWuthAtmostKDistinct(string s, int k) {\n        int size = s.length();\n        int start = 0, end = 0;\n        int len = 0, ans = 0;\n        unordered_map<char, int> mp;\n        \n        while(end < size)\n        {\n            if(mp[s[end]] == 0) // distinct\n            {\n                k--;\n            }\n            \n            if(k >= 0)\n            {\n                len++;\n                mp[s[end++]];\n                ans = max(ans, len);\n            }\n            \n            else\n            {\n                mp[s[end]]++;\n                while(k < 0)\n                {\n                    if(mp[s[start]] == 1)\n                    {\n                        k++;\n                    }\n                    mp[s[start]]--;\n                    start++;\n                    len = end - start + 1;\n                }\n            }\n            end++;\n        }\n        if(ans != 0) {\n            return s.substr(start, end - start + 1);\n        }\n    return "";\n    }\n```\n* **Coming to question of exactly k distinct characters**. Let\'s say we have k = 3.\n* Then the above problem will consider all the string with **AtMost(k) = AtMost(2) = 3 distinct + 2 distinct + 1 distinct + 0 distinct**\n* And if we run the same above function for k-1 ie., for k = 2.it will consider all the strings with **AtMost(k-1) = AtMost(2) = 2 distinct + 1 distinct + 0 distinct**\n* **There\'s a great observation here.** \n\t**Atmost(3) - Atmost (2) = (3 distinct + 2 distinct + 1 distinct + 0 distinct) - (2 distinct + 1 distinct + 0 distinct) = 3 disinct = exactly k distinct.**\n\t\n\t#### \t\t\t***CODE FOR SUBARRAYS WITH K DIFFERENT INTEGERS***\n\t\n```\n int subarraysWithAtMostKDistinct(vector<int> nums, int k)\n{\n\tunordered_map<int, int> freq;\n\tint size = nums.size();\n\tint start = 0, end = 0;\n\tint total = 0;\n\n\twhile(end < size)\n\t{\n\t\tif(freq[nums[end]] == 0) // distinct\n\t\t{\n\t\t\tk--;\n\t\t}\n\n\t\tif(k >= 0)\n\t\t{\n\t\t\tfreq[nums[end]]++;\n\t\t}\n\n\t\telse\n\t\t{\n\t\t\tfreq[nums[end]]++;\n\t\t\twhile(k < 0)\n\t\t\t{\n\t\t\t\tif(freq[nums[start]] == 1)\n\t\t\t\t{\n\t\t\t\t\tk++;\n\t\t\t\t}\n\t\t\t\tfreq[nums[start]]--;\n\t\t\t\tstart++;\n\t\t\t}\n\t\t}\n\t\tend++;\n\t\ttotal += end-start+-1;\n\t}\n\n\treturn total;\n}\n\nint subarraysWithKDistinct(vector<int>& nums, int k) {\n\tint atMostKdistinct = subarraysWithAtMostKDistinct(nums, k);\n\n\tint atMostK_1distinct = subarraysWithAtMostKDistinct(nums, k-1);\n\n\treturn atMostKdistinct - atMostK_1distinct;\n}\n```\n\n\n\t\t\t
['C', 'Sliding Window']