2pointers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6613fc96-c18c-4cab-8c95-a23874d861bf",
   "metadata": {
    "tags": []
   },
   "source": [
    "# 16. 2 Sum or variant or 3 Sum Closest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16d132f0-2063-496c-942d-c076384a5044",
   "metadata": {},
   "outputs": [],
   "source": [
    "def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 3:\n",
    "            return sum(nums)\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        diff = float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            lo, hi = i+1, len(nums)-1\n",
    "            while lo < hi:\n",
    "                summ = nums[i]+nums[lo]+nums[hi]\n",
    "                if abs(target-summ) < abs(diff):\n",
    "                    diff = target-summ\n",
    "                elif summ < target:\n",
    "                    lo+=1\n",
    "                else:\n",
    "                    hi-=1\n",
    "            if diff == 0:\n",
    "                break\n",
    "        return target-diff"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef2b81d9-0d8c-455a-8328-b77051f907f1",
   "metadata": {},
   "source": [
    "# 15. 3Sum\n",
    "nums[i] + nums[j] + nums[k] == 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9db7c5b6-6b06-4a7a-8225-d17d8844fec4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "    nums.sort()\n",
    "    res = []\n",
    "\n",
    "    # def twoSumII(nums, i, res):\n",
    "    #     lo, hi = i+1, len(nums)-1\n",
    "    #     while lo < hi:\n",
    "    #         summ = nums[i] + nums[lo] + nums[hi]\n",
    "    #         if summ < 0:\n",
    "    #             lo+=1 \n",
    "    #         elif summ > 0:\n",
    "    #             hi-=1 \n",
    "    #         else:\n",
    "    #             res.append([nums[i], nums[lo], nums[hi]])\n",
    "    #             lo+=1\n",
    "    #             hi-=1\n",
    "    #             while lo < hi and nums[lo] == nums[lo -1]:\n",
    "    #                 lo +=1\n",
    "    def twoSum(nums, i, res):\n",
    "        seen = set()\n",
    "        j = i + 1\n",
    "        while j < len(nums):\n",
    "            complement = -nums[i] - nums[j]\n",
    "            if complement in seen:\n",
    "                res.append([nums[i], nums[j], complement])\n",
    "                while j + 1 < len(nums) and nums[j] == nums[j+1]:\n",
    "                    j +=1 \n",
    "            seen.add(nums[j])\n",
    "            j +=1 \n",
    "\n",
    "    for i in range(len(nums)):\n",
    "        if nums[i] > 0:\n",
    "            break\n",
    "        if i == 0 or nums[i-1] != nums[i]:\n",
    "            twoSum(nums, i, res)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2d5b86f-2331-4a0d-9480-bda823820d2e",
   "metadata": {},
   "source": [
    "# 38. Count and Say\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e45cc972-d5bc-4097-b862-61cfaaebcc81",
   "metadata": {},
   "source": [
    "The count-and-say sequence is a sequence of digit strings defined by the recursive formula:\n",
    "\n",
    "countAndSay(1) = \"1\"\n",
    "countAndSay(n) is the way you would \"say\" the digit string from countAndSay(n-1), which is then converted into a different digit string.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6c3f3f85-b20e-4a2e-81bc-1c34a7854f0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countAndSay(self, n: int) -> str:\n",
    "    current_string = '1'\n",
    "    for _ in range(n - 1):\n",
    "        next_string = ''\n",
    "        j = 0\n",
    "        k = 0\n",
    "        while j < len(current_string):\n",
    "            while (k < len(current_string) and current_string[k] == current_string[j]):\n",
    "                k += 1\n",
    "            next_string += str(k - j) + current_string[j]\n",
    "            j = k\n",
    "        current_string = next_string\n",
    "    return current_string"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f710503c-dd5c-4d31-a200-8378401964b5",
   "metadata": {},
   "source": [
    "# 76. Minimum Window Substring\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36465c0e-fab5-4f09-af68-cf7c584653e4",
   "metadata": {},
   "source": [
    "Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string \"\".\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "198a56cf-2fb9-454f-ab2e-8e161a40c25c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minWindow(self, s: str, t: str) -> str:\n",
    "    count_t = Counter(t)\n",
    "    count_s = Counter(s)\n",
    "    if len(s)<len(t):\n",
    "        return \"\"\n",
    "\n",
    "    elif len(s)==len(t):\n",
    "        if count_s == count_t:\n",
    "            return s\n",
    "        else:\n",
    "            return \"\"\n",
    "    else:\n",
    "        for char_t in count_t:\n",
    "            if char_t not in count_s:\n",
    "                return \"\"\n",
    "        required = len(count_t)\n",
    "        l, r = 0, 0\n",
    "        formed = 0\n",
    "        window_counts = {}\n",
    "        ans = float(\"inf\"), None, None\n",
    "        while r < len(s):\n",
    "            char = s[r]\n",
    "            window_counts[char] = window_counts.get(char, 0)+1\n",
    "            if char in count_t and window_counts[char] == count_t[char]:\n",
    "                formed+=1\n",
    "            while l <= r and formed == required:\n",
    "                char = s[l]\n",
    "                if r - l + 1 < ans[0]:\n",
    "                    ans = (r-l +1, l, r)\n",
    "                window_counts[char]-=1\n",
    "                if char in count_t and window_counts[char] < count_t[char]:\n",
    "                    formed-=1\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return \"\" if ans[0] == float(\"inf\") else s[ans[1]:ans[2] +1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e05fc19-dc54-4d6c-883c-619578cef9b8",
   "metadata": {},
   "source": [
    "# 680. Valid Palindrome II\n",
    "Given a string s, return true if the s can be palindrome after deleting at most one character from it.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "26496a5d-c3ed-468b-938b-f356548241c6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def validPalindrome(self, s: str) -> bool:\n",
    "    def check_palindrome(s, i, j):\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "\n",
    "        return True\n",
    "    i = 0\n",
    "    j = len(s) - 1\n",
    "    while i < j:\n",
    "        # Found a mismatched pair - try both deletions\n",
    "        if s[i] != s[j]:\n",
    "            return check_palindrome(s, i, j - 1) or check_palindrome(s, i + 1, j)\n",
    "        i += 1\n",
    "        j -= 1\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "231797b7-cb6f-4ce2-8465-0d515139db7f",
   "metadata": {},
   "source": [
    "# 142. Linked List Cycle II\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f40d4c0-13ff-41c4-a71e-59ceaf19cac0",
   "metadata": {},
   "outputs": [],
   "source": [
    "Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.\n",
    "\n",
    "There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.\n",
    "\n",
    "Do not modify the linked list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c169863d-4a65-4654-80c0-029b0cbf5374",
   "metadata": {},
   "outputs": [],
   "source": [
    "def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return None\n",
    "        def getIntersect(head):\n",
    "            tortoise = head\n",
    "            hare = head\n",
    "\n",
    "            # A fast pointer will either loop around a cycle and meet the slow\n",
    "            # pointer or reach the `null` at the end of a non-cyclic list.\n",
    "            while hare is not None and hare.next is not None:\n",
    "                tortoise = tortoise.next\n",
    "                hare = hare.next.next\n",
    "                if tortoise == hare:\n",
    "                    return tortoise\n",
    "\n",
    "            return None\n",
    "\n",
    "        # If there is a cycle, the fast/slow pointers will intersect at some\n",
    "        # node. Otherwise, there is no cycle, so we cannot find an entrance to\n",
    "        # a cycle.\n",
    "        intersect = getIntersect(head)\n",
    "        if intersect is None:\n",
    "            return None\n",
    "\n",
    "        # To find the entrance to the cycle, we have two pointers traverse at\n",
    "        # the same speed -- one from the front of the list, and the other from\n",
    "        # the point of intersection.\n",
    "        ptr1 = head\n",
    "        ptr2 = intersect\n",
    "        while ptr1 != ptr2:\n",
    "            ptr1 = ptr1.next\n",
    "            ptr2 = ptr2.next\n",
    "\n",
    "        return ptr1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30fc5c97-dbd1-439c-b899-0660ad24b537",
   "metadata": {},
   "source": [
    "# 649. Dota2 Senate\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6d13c63-12be-4716-b776-801409d6d01a",
   "metadata": {},
   "source": [
    "In the world of Dota2, there are two parties: the Radiant and the Dire.\n",
    "\n",
    "The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:\n",
    "\n",
    "Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.\n",
    "Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.\n",
    "Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.\n",
    "\n",
    "The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.\n",
    "\n",
    "Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be \"Radiant\" or \"Dire\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2466bf5f-916d-4ce2-96e8-c5c87fcae0b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def predictPartyVictory(self, senate: str) -> str:\n",
    "    radiant, dire = [], []\n",
    "    for idx, s in enumerate(senate):\n",
    "        if s == 'R':\n",
    "            radiant.append(idx)\n",
    "        else:\n",
    "            dire.append(idx)\n",
    "\n",
    "    while radiant and dire:\n",
    "        if radiant[0] < dire[0]:\n",
    "            radiant.append(radiant[0] + len(senate))\n",
    "        else:\n",
    "            dire.append(dire[0] + len(senate))\n",
    "        radiant.pop(0)\n",
    "        dire.pop(0)\n",
    "\n",
    "    return \"Radiant\" if radiant else \"Dire\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e49f776-8107-46e3-82bf-ce559e9f33ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "def predictPartyVictory(self, senate: str) -> str:\n",
    "        r_count = senate.count('R')\n",
    "        d_count = len(senate) - r_count\n",
    "\n",
    "        # Floating Ban Count\n",
    "        d_floating_ban = 0\n",
    "        r_floating_ban = 0\n",
    "\n",
    "        # Queue of Senators\n",
    "        q = deque(senate)\n",
    "\n",
    "        # While any party has eligible Senators\n",
    "        while r_count and d_count:\n",
    "\n",
    "            # Pop the senator with turn\n",
    "            curr = q.popleft()\n",
    "\n",
    "            # If eligible, float the ban on the other party, enqueue again.\n",
    "            # If not, decrement the floating ban and count of the party.\n",
    "            if curr == 'D':\n",
    "                if d_floating_ban:\n",
    "                    d_floating_ban -= 1\n",
    "                    d_count -= 1\n",
    "                else:\n",
    "                    r_floating_ban += 1\n",
    "                    q.append('D')\n",
    "            else:\n",
    "                if r_floating_ban:\n",
    "                    r_floating_ban -= 1\n",
    "                    r_count -= 1\n",
    "                else:\n",
    "                    d_floating_ban += 1\n",
    "                    q.append('R')\n",
    "\n",
    "        # Return the party with eligible Senators\n",
    "        return 'Radiant' if r_count else 'Dire'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1476cc1-dbce-4478-b73f-30e038ea5b2b",
   "metadata": {},
   "source": [
    "#### Remark\n",
    "ChatGPT can do it, earlier numbered, probably seen the ans. The point is to figure out the greedy solution's mechanism. Floating vote mechanism needs to be based on 2 queues solution."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fba1b3c-0266-4605-b258-6f5dda3a01ca",
   "metadata": {},
   "source": [
    "# 1456. Maximum Number of Vowels in a Substring of Given Length\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c68e9704-c45b-48d9-8bb3-9f22d0af5904",
   "metadata": {},
   "source": [
    "Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.\n",
    "\n",
    "Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.\n",
    "\n",
    "#### Remark:\n",
    "This one is pretty easy, typical pattern of sliding window. ChatGPT can do it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48c1e683-c5df-4b62-9eea-0975835d5ede",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxVowels(self, s: str, k: int) -> int:\n",
    "    # vowels = \"aeiou\"\n",
    "    # # print(len(s))\n",
    "    # prefix_vowels = []\n",
    "    # count = 0\n",
    "    # for char in s:\n",
    "    #     if char in vowels:\n",
    "    #         count += 1\n",
    "    #     prefix_vowels.append(count)\n",
    "    # if k>= len(s):\n",
    "    #     return prefix_vowels[-1]\n",
    "\n",
    "    # # print(prefix_vowels)\n",
    "    # res = 0\n",
    "    # res = max(prefix_vowels[k-1], res)\n",
    "    # for i in range(1, len(prefix_vowels)-k+1):\n",
    "    #     res = max(prefix_vowels[i+k-1]-prefix_vowels[i-1], res)\n",
    "    # return res\n",
    "    vowels = set(['a', 'e', 'i', 'o', 'u'])\n",
    "    max_vowels = 0\n",
    "    current_vowels = 0\n",
    "\n",
    "    # Count vowels in first k characters\n",
    "    for i in range(k):\n",
    "        if s[i] in vowels:\n",
    "            current_vowels += 1\n",
    "\n",
    "    max_vowels = current_vowels\n",
    "\n",
    "    # Slide window and count vowels in each substring\n",
    "    for i in range(k, len(s)):\n",
    "        if s[i-k] in vowels:\n",
    "            current_vowels -= 1\n",
    "        if s[i] in vowels:\n",
    "            current_vowels += 1\n",
    "        max_vowels = max(max_vowels, current_vowels)\n",
    "\n",
    "    return max_vowels\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8648ec4c-ea81-4ce0-87ad-90f1259c3d0f",
   "metadata": {},
   "source": [
    "# 1498. Number of Subsequences That Satisfy the Given Sum Condition\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6de99eae-80ae-4316-9301-7e8a06cf3e71",
   "metadata": {},
   "source": [
    "You are given an array of integers nums and an integer target.\n",
    "\n",
    "Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 109 + 7.\n",
    "\n",
    "#### ChatGPT3.5 could do it, first time GPT4 failed, GPT4 gave very weird prefix_sum style answer than were short by 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e498c7eb-c4f1-46d9-afee-73771b259e68",
   "metadata": {},
   "outputs": [],
   "source": [
    " def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        \n",
    "        answer = 0\n",
    "        \n",
    "        for left in range(n):\n",
    "            # Find the insertion position for `target - nums[left]`\n",
    "            # 'right' equals the insertion index minus 1.\n",
    "            right = bisect.bisect_right(nums, target - nums[left]) - 1\n",
    "            if right >= left:\n",
    "                answer += pow(2, right - left, mod)\n",
    "            \n",
    "        return answer % mod\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c5e4a234-89e6-4075-9dfa-88be5fb15187",
   "metadata": {},
   "outputs": [],
   "source": [
    "def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        i, j = 0, n-1\n",
    "        while i <= j:\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                count += pow(2, j-i)\n",
    "                # print(count)\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return count % MOD"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd2e0f64-b81d-49d9-8332-01ea97415541",
   "metadata": {},
   "source": [
    "# 209. Minimum Size Subarray Sum\n",
    "Given an array of positive integers nums and a positive integer target, return the minimal length of a \n",
    "subarray\n",
    " whose sum is greater than or equal to target. If there is no such subarray, return 0 instead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dceca7fb-9496-4113-9f47-1b80555adc2a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "    min_length = float('inf')\n",
    "    left = 0\n",
    "    current_sum = 0\n",
    "\n",
    "    for right in range(len(nums)):\n",
    "        current_sum += nums[right]\n",
    "\n",
    "        while current_sum >= target:\n",
    "            min_length = min(min_length, right - left + 1)\n",
    "            current_sum -= nums[left]\n",
    "            left += 1\n",
    "\n",
    "    return min_length if min_length != float('inf') else 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0940918-9d3c-417d-8cea-174c801a2d1f",
   "metadata": {},
   "source": [
    "# 1493. Longest Subarray of 1's After Deleting One Element\n",
    "Given a binary array nums, you should delete one element from it.\n",
    "\n",
    "Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67efe750-8818-4496-9a8a-71216a15e320",
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestSubarray(self, nums: List[int]) -> int:\n",
    "    left = 0\n",
    "    zeroes = 0\n",
    "    max_length = 0\n",
    "\n",
    "    # Iterating through the array\n",
    "    for right in range(len(nums)):\n",
    "        if nums[right] == 0:\n",
    "            zeroes += 1\n",
    "\n",
    "        # Maintain the window to contain only 1 zero\n",
    "        while zeroes > 1:\n",
    "            if nums[left] == 0:\n",
    "                zeroes -= 1\n",
    "            left += 1\n",
    "\n",
    "        max_length = max(max_length, right - left + 1)\n",
    "\n",
    "    # Return the maximum length subtracted by 1 (since we need to delete one element)\n",
    "    return max_length - 1 if max_length else 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ecaac7ce-ce27-4401-b011-73340d9ceab5",
   "metadata": {},
   "source": [
    "# 2024. Maximize the Confusion of an Exam\n",
    "A teacher is writing a test with n true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).\n",
    "\n",
    "You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:\n",
    "\n",
    "Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').\n",
    "Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b4d5556a-2477-47a5-9bfc-bbe60d6139cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "    # ans = list(answerKey)\n",
    "    # n = len(ans)\n",
    "    # max_len = max_true = max_false = 0\n",
    "    # left_true = left_false = 0\n",
    "\n",
    "    # for right in range(n):\n",
    "    #     if answerKey[right] == 'T':\n",
    "    #         max_true += 1\n",
    "    #     else:\n",
    "    #         max_false += 1\n",
    "    #     while right - left_true + 1 - max_true > k:\n",
    "    #         if answerKey[left_true] == 'T':\n",
    "    #             max_true -= 1\n",
    "    #         left_true += 1\n",
    "    #     while right - left_false + 1 - max_false > k:\n",
    "    #         if answerKey[left_false] == 'F':\n",
    "    #             max_false -= 1\n",
    "    #         left_false += 1\n",
    "    #     max_len = max(max_len, right - left_true + 1, right - left_false + 1)\n",
    "    # return max_len\n",
    "    max_size = k\n",
    "    count = collections.Counter(answerKey[:k])\n",
    "\n",
    "    left = 0\n",
    "    for right in range(k, len(answerKey)):\n",
    "        count[answerKey[right]] += 1\n",
    "\n",
    "        while min(count['T'], count['F']) > k: \n",
    "            count[answerKey[left]] -= 1\n",
    "            left += 1\n",
    "\n",
    "        max_size = max(max_size, right - left + 1)\n",
    "\n",
    "    return max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a6f15ef-211a-47fb-84f6-4155c52d5b59",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:\n",
    "    max_size = 0\n",
    "    count = collections.Counter()\n",
    "\n",
    "    for right in range(len(answerKey)):\n",
    "        count[answerKey[right]] += 1\n",
    "        minor = min(count['T'], count['F'])\n",
    "\n",
    "        if minor <= k:\n",
    "            max_size += 1\n",
    "        else:\n",
    "            count[answerKey[right - max_size]] -= 1 # faster solution since we don't have to go back down to smaller window than max_size\n",
    "\n",
    "    return max_size"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}