Different Python two-pointer solutions
Please see and vote for my solutions for these similar problems.\n1208. Get Equal Substrings Within Budget\n3. Longest Substring Without Repeating Characters\n1
Please see and vote for my solutions for these similar problems.\n[1208. Get Equal Substrings Within Budget](https://leetcode.com/problems/get-equal-substrings-within-budget/discuss/392901/Simple-Python-moving-window)\n[3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/348137/Simple-Python-two-pointer-solution-(52ms-beat-97.94))\n[159. Longest Substring with At Most Two Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/348157/Simple-Python-two-pointer-solution)\n[340. Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/discuss/348216/Simple-Python-two-pointer-solution-(72-ms-beat-94.93))\n[992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/discuss/348984/Different-Python-two-pointer-solutions)\n[424. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/discuss/363071/Simple-Python-two-pointer-solution)\n[209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/discuss/344476/Simple-Python-two-pointer-solution)\n[713. Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/discuss/344245/Simple-Python-solution-(beat-94.59))\n[76. Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/discuss/344533/Simple-Python-two-pointer-solution)\n\nSolution 1: \nKeep a moving window expand while it contains less than k distinct integers, \nthen shrink while it contains k + 1 distinct integers. \nOnly save the right-most positions of distinct integers.\nFor fixed ending at right, the window contains k distinct integers if the left end is between [left, left_k]. \n\nTime complexity: O(n * K) (Time Limit Exceeded, 52 / 55 test cases passed.)\n```\n    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:\n        if K == 0 or len(A) < K:\n            return 0\n        res = 0\n        left, left_k = 0, 0\n        right_most_pos = dict()\n        for right in range(len(A)):\n            right_most_pos[A[right]] = right\n            if len(right_most_pos) == K + 1:\n                left_k = min(right_most_pos.values())\n                right_most_pos.pop(A[left_k])\n                left_k += 1\n                left = left_k\n            if len(right_most_pos) == K:\n                left_k = min(right_most_pos.values())\n                res += left_k - left + 1\n        return res\n```\n\nSolution 2: use bisect to improve the efficiency of min(right_most_pos.values())\nTime complexity: O(n * K) (512 ms, beat 85.48%)\n```\n    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:\n        if K == 0 or len(A) < K:\n            return 0\n        res = 0\n        left, left_k = 0, 0\n        sorted_pos = []\n        right_most_pos = dict()\n        for right in range(len(A)):\n            if A[right] in right_most_pos:\n                ind = bisect.bisect_left(sorted_pos, right_most_pos[A[right]])\n                sorted_pos.pop(ind)\n            sorted_pos.append(right)\n            right_most_pos[A[right]] = right\n            if len(right_most_pos) == K + 1:\n                left_k = sorted_pos.pop(0)\n                right_most_pos.pop(A[left_k])\n                left_k += 1\n                left = left_k\n            if len(right_most_pos) == K:\n                left_k = sorted_pos[0]\n                res += left_k - left + 1\n        return res\n```\n\nSolution 3: instead of saving the right-most positions of distinct integers, we save their frequences\nTime complexity: O(n) (424 ms, beat 95.16%)\n```\n    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:\n        if K == 0 or len(A) < K:\n            return 0\n        res = 0\n        left, left_k = 0, 0\n        counter = dict()\n        for right in range(len(A)):\n            counter[A[right]] = counter.get(A[right], 0) + 1\n            if len(counter) == K + 1:\n                counter.pop(A[left_k])\n                left_k += 1\n                left = left_k\n            if len(counter) == K:\n                while counter[A[left_k]] > 1:\n                    counter[A[left_k]] -= 1\n                    left_k += 1\n                res += left_k - left + 1\n        return res\n```\n\t\t\nSolution 4: two-pass solution\nTime complexity O(n), (584 ms, beat 62.90%)\n```\nclass Solution:\n    def subarraysWithKDistinct(self, A, K):\n        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n\n    def atMostK(self, A, K):\n        counter = dict()\n        res = 0\n        left = 0\n        for right in range(len(A)):\n            counter[A[right]] = counter.get(A[right], 0) + 1\n            while len(counter) > K:\n                counter[A[left]] -= 1\n                if counter[A[left]] == 0:\n                    counter.pop(A[left])\n                left += 1\n            res += right - left + 1\n        return res\n```
[]