Longest - Shortest
If the problem talks about continuous subarrays or substrings, the sliding window technique may help solve it in a linear time. Such problems are tricky, though
If the problem talks about continuous subarrays or substrings, the sliding window technique may help solve it in a linear time. Such problems are tricky, though the solution is simple once you get it. No wonder I am seeing such problems in almost every interview!\n\nHere, we will take a look at [Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/) (LeetCode Hard), which appeared on LeetCode [weekly contest #123](https://leetcode.com/contest/weekly-contest-123). You can also master the sliding windows technique with these additional problems:\n- [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)\n- [Longest Substring with At Most Two Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/)\n- [Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/)\n<!--# Problem Description\nGiven an array ```A``` of positive integers, call a (contiguous, not necessarily distinct) subarray of ```A``` good if the number of different integers in that subarray is exactly ```K```. For example, ```[1,2,3,1,2]``` has 3 different integers: 1, 2, and 3.\n\nReturn the number of good subarrays of ```A```.\n### Example\n**Input:** A = [1,2,1,2,3], K = 2\n**Output:** 7\n**Explanation:** Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].\n# Coding Practice\nTry solving this problem before moving on to the solutions. It is available on LeetCode Online Judge ([Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/)). Also, as you read through a solution, try implementing it yourself.\n\nLeetCode is my favorite destinations for algorithmic problems. It has 987 problems and counting, with test cases to validate the correctness, as well as computational and memory complexity. There is also a large community discussing different approaches, tips and tricks.\n# Brute-Force Solution\nWe can just iterate through each sub-array using two loops and count the good ones. For the inner loop, we use hash set to count unique numbers; if we the set size becomes larger than ```K```, we break from the inner loop.\n```\nint subarraysWithKDistinct(vector<int>& A, int K, int res = 0) {\n  for (auto i = 0; i < A.size(); ++i) {\n    unordered_set<int> s;\n    for (auto j = i; j < A.size() && s.size() <= K; ++j) {\n      s.insert(A[j]);\n      if (s.size() == K) ++res;\n    }\n  }\n  return res;\n}\n```\n### Complexity Analysis\nThe time complexity of this solution is *O(n * n)*, where *n* is the length of ```A```. This solution is not accepted by the online judge.\n-->\n# Intuition\nFor numbers `l`, `m`, and `r` (`l <= m <= r`), such as:\n- `[l, r]` is the longest subarray with `k` unique numbers, and\n- `[m, r]` is the shortest subarray with `k` unique numbers,\n\nthere are `m - l + 1` good subarrays that end at `r`.\n\nFor example, for `k == 3` and array `[1, 2, 1, 2, 3]`, the longest subarray is `[0, 4]` and shortest - `[2, 4]`.  So, we have `2 - 0 + 1 == 3` good subarrays: `[1, 2, 1, 2, 3]`, `[2, 1, 2, 3]` and `[1, 2, 3]`.\n# Linear Solution\nWe can iterate through the array and use three pointers for our sliding window (`[l, m, r]`). The back of the window is always the current position in the array (`r`). The middle of the window (`m`) is moved so that `nums[m]` appear only once in `[m, r]`.\n\nThis ensures that `[m, r]` is the shortest subarray with a given number of unique elements.\n\nTo do that, we keep tabs on how many times each number appears in our window (`cnt`). After we add next number to the back of our window, we try to move `m` as far as possible while maintaining the same number of unique elements.\n\nIf we collected `k` unique numbers, then we found `m - l + 1` good subarrays.\n\nIf our window reached `k + 1` unique numbers, we reduce set `cnt[nums[m]]` to zero (again, that number appears only at `nums[m]`), increment `m` and set `l = m + 1` (because we are starting a new sequence). This process is demonstrated step-by-step for the test case below; `m - l + 1` window is shown as `+1` in the green background.\n```\n[5,7,5,2,3,3,4,1,5,2,7,4,6,2,3,8,4,5,7]\n7\n```\n![image](https://assets.leetcode.com/users/votrubac/image_1549876616.png)\n\n**C++**\n```cpp\nint subarraysWithKDistinct(vector<int>& nums, int k) {\n    int cnt[20001] = {}, res = 0, sz = nums.size();\n    for (int l = 0, m = 0, r = 0; r < sz; ++r) {\n        if (++cnt[nums[r]] == 1)\n            if (--k < 0) {\n                cnt[nums[m++]] = 0;\n                l = m;\n            }\n        if (k <= 0) {\n            while (cnt[nums[m]] > 1)\n                --cnt[nums[m++]];\n            res += m - l + 1;   \n        }\n    }\n    return res;\n} \n```\n**Java**\n```java\npublic int subarraysWithKDistinct(int[] nums, int k) {\n    int res = 0, sz = nums.length;\n    int[] cnt = new int[sz + 1];\n    for (int l = 0, m = 0, r = 0; r < sz; ++r) {\n        if (++cnt[nums[r]] == 1)\n            if (--k < 0) {\n                cnt[nums[m++]] = 0;\n                l = m;\n            }\n        if (k <= 0) {\n            while (cnt[nums[m]] > 1)\n                --cnt[nums[m++]];\n            res += m - l + 1;   \n        }\n    }    \n    return res;\n}\n```\n**Python 3**\n```python\nclass Solution:\n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        cnt, res, l, m = [0] * (len(nums) + 1), 0, 0, 0\n        for n in nums:\n            cnt[n] += 1\n            if cnt[n] == 1:\n                k -= 1\n                if (k < 0):\n                    cnt[nums[m]] = 0\n                    m += 1\n                    l = m\n            if k <= 0:\n                while(cnt[nums[m]] > 1):\n                    cnt[nums[m]] -= 1\n                    m += 1\n                res += m - l + 1\n        return res\n```\n### Complexity Analysis\n- Time Complexity: *O(n)*, where *n* is the length of ```A```.\n- Space Complexity: *O(n)*.
['C', 'Java', 'Python3']