medium_tasks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# String Compression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "https://leetcode.com/problems/string-compression/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Given an array of characters chars, compress it using the following algorithm:\n",
    "\n",
    "Begin with an empty string s. For each group of consecutive repeating characters in chars:\n",
    "\n",
    "If the group's length is 1, append the character to s.\n",
    "Otherwise, append the character followed by the group's length.\n",
    "The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.\n",
    "\n",
    "After you are done modifying the input array, return the new length of the array.\n",
    "\n",
    "You must write an algorithm that uses only constant extra space.  \n",
    "\n",
    "Input: chars = [\"a\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\"]  \n",
    "Output: Return 4, and the first 4 characters of the input array should be: [\"a\",\"b\",\"1\",\"2\"].  \n",
    "Explanation: The groups are \"a\" and \"bbbbbbbbbbbb\". This compresses to \"ab12\".  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def compress(chars: list) -> int:\n",
    "    chars.append('')\n",
    "    len_chars = len(chars) #3\n",
    "    cnt_index = 0 #2\n",
    "    cnt_groups = 1 #2\n",
    "    for i in range(len_chars-1):\n",
    "        current_letter=chars[i]\n",
    "        if chars[i] == chars[i+1]:\n",
    "            cnt_groups += 1              \n",
    "        else:\n",
    "            if cnt_groups>1:\n",
    "                cnt_index += 1\n",
    "                chars[cnt_index-1] = current_letter\n",
    "                chars[cnt_index:cnt_index+len(list(str(cnt_groups)))] = list(str(cnt_groups))\n",
    "                cnt_index+=(len(list(str(cnt_groups))))\n",
    "            else:\n",
    "                chars[cnt_index] = current_letter\n",
    "                cnt_index +=1\n",
    "            cnt_groups = 1 \n",
    "    chars.pop(len_chars-1)\n",
    "    print(chars[:cnt_index])\n",
    "    return cnt_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', '2', 'b', '2', 'c', '3']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chars = [\"a\",\"a\",\"b\",\"b\",\"c\",\"c\",\"c\"]\n",
    "compress(chars)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Longest Substring Without Repeating Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "https://leetcode.com/problems/longest-substring-without-repeating-characters/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Given a string s, find the length of the longest substring without repeating characters.  \n",
    "  \n",
    "Input: s = \"abcabcbb\"  \n",
    "Output: 3  \n",
    "Explanation: The answer is \"abc\", with the length of 3.  \n",
    "    \n",
    "Input: s = \"pwwkew\"  \n",
    "Output: 3  \n",
    "Explanation: The answer is \"wke\", with the length of 3.  \n",
    "Notice that the answer must be a substring, \"pwke\" is a subsequence and not a substring.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 234,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring(s: str) -> int:\n",
    "    lengths_of_substring = []\n",
    "    if len(s) == 1:\n",
    "        return 1\n",
    "    cnt_lenght = 0\n",
    "    cnt_lenght_all =[]\n",
    "    dict_of_letters = {}\n",
    "    for ind in range(len(s)):\n",
    "        new_list = s[ind:]\n",
    "        for i in new_list:\n",
    "            if i not in dict_of_letters:\n",
    "                dict_of_letters[i]=1\n",
    "                cnt_lenght+=1\n",
    "            else:\n",
    "                dict_of_letters = {}\n",
    "                dict_of_letters[i]=1\n",
    "                cnt_lenght_all.append(cnt_lenght)\n",
    "                cnt_lenght = 1\n",
    "                break\n",
    "            cnt_lenght_all.append(cnt_lenght)\n",
    "        cnt_lenght = 0\n",
    "        dict_of_letters = {}\n",
    "    if cnt_lenght_all == []:\n",
    "        return 0\n",
    "    else:\n",
    "        return max(cnt_lenght_all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 251,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 251,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Word search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/word-search/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an m x n grid of characters board and a string word, return true if word exists in the grid.  \n",
    "\n",
    "The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once   \n",
    "\n",
    "Input: board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"ABCCED\"  \n",
    "Output: true  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First version, very ugly code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 485,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 485,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def go_right(board, word, i, j,prev_list, k):\n",
    "    if ((i, j+1) not in prev_list):\n",
    "            if ((j+1) < len(board[0])):\n",
    "                if (board[i][j+1] == word[k]):\n",
    "                    if k==len(word)-1:\n",
    "                        return 'found'\n",
    "                    else:\n",
    "#                         prev_list.append((i, j))\n",
    "                        return make_step(board, word, i, j+1, k+1, prev_list)\n",
    "def go_left(board, word, i, j,prev_list, k):\n",
    "     if ((i, j-1) not in prev_list):\n",
    "            if ((j-1) >= 0):\n",
    "                if (board[i][j-1] == word[k]):\n",
    "                    if k==len(word)-1:\n",
    "                        return 'found'\n",
    "                    else:\n",
    "#                         prev_list.append((i, j))\n",
    "                        return make_step(board, word, i, j-1, k+1, prev_list)\n",
    "def go_up(board, word, i, j,prev_list, k):\n",
    "     if ((i-1, j) not in prev_list):\n",
    "            if ((i-1) >= 0):\n",
    "                if (board[i-1][j] == word[k]):\n",
    "                    if k==len(word)-1:\n",
    "                        return 'found'\n",
    "                    else:\n",
    "#                         prev_list.append((i, j))\n",
    "                        return make_step(board, word, i-1, j, k+1, prev_list)\n",
    "def go_down(board, word, i, j,prev_list, k):\n",
    "     if ((i+1, j) not in prev_list):\n",
    "            if ((i+1) <  len(board)):\n",
    "                if (board[i+1][j] == word[k]):\n",
    "                    if k==len(word)-1:\n",
    "                        return 'found'\n",
    "                    else:\n",
    "#                         prev_list.append((i, j))\n",
    "                        return make_step(board, word, i+1, j, k+1, prev_list)\n",
    "\n",
    "def make_step(board, word, i, j, k, prev_list):\n",
    "    while (k < len(word)):\n",
    "        prev_list.append((i, j))\n",
    "        status = go_right(board, word, i, j, prev_list, k)\n",
    "        if status == 'found':\n",
    "            break\n",
    "#         else:\n",
    "#             prev_list = prev_list[:-1]\n",
    "        status = go_left(board, word, i, j, prev_list, k)\n",
    "        if status == 'found':\n",
    "            break\n",
    "#         else:\n",
    "#             prev_list = prev_list[:-1]\n",
    "        status = go_up(board, word, i, j, prev_list, k)\n",
    "        if status == 'found':\n",
    "            break\n",
    "#         else:\n",
    "#             prev_list = prev_list[:-1]\n",
    "        status = go_down(board, word, i, j, prev_list, k)     \n",
    "        if status == 'found':\n",
    "            break\n",
    "#         else:\n",
    "#             prev_list = prev_list[:-1]\n",
    "        prev_list.pop()\n",
    "        return 'not found' \n",
    "    return 'found'\n",
    "        \n",
    "def word_search(board, word):\n",
    "    for i in range(len(board)):\n",
    "        for j in range(len(board[0])):\n",
    "            if board[i][j] == word[0]:       \n",
    "                status = make_step(board, word, i, j, 1, [])\n",
    "                if status == 'found':\n",
    "                    return True\n",
    "                    \n",
    "    return False\n",
    "\n",
    "#word_search([[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]],\"ABCB\")\n",
    "word_search([[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"E\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]],\n",
    "\"ABCESEEEFS\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beautiful version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 539,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_step(board, word, i, j, k, prev_list):\n",
    "    if (i,j) in prev_list:\n",
    "        return False\n",
    "    if (i < 0):\n",
    "        return False\n",
    "    if (j < 0):\n",
    "        return False\n",
    "    if (i>=len(board)):\n",
    "        return False\n",
    "    if (j>=len(board[0])):\n",
    "        return False\n",
    "    if board[i][j] != word[k]:\n",
    "        return False\n",
    "    prev_list.append((i, j))\n",
    "    possible_steps = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]\n",
    "    for step in possible_steps:\n",
    "        if k == len(word)-1:\n",
    "            return True\n",
    "        else:\n",
    "            found = make_step(board, word, step[0], step[1], k+1, prev_list)\n",
    "            if found:\n",
    "                return True\n",
    "    prev_list.pop()\n",
    "    return False\n",
    "\n",
    "def word_search(board, word):\n",
    "    for i in range(len(board)):\n",
    "        for j in range(len(board[0])):\n",
    "            status = make_step(board, word, i, j, 0, [])\n",
    "            if status:\n",
    "                return True\n",
    "                    \n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 541,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 541,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_search([[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"E\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]],\n",
    "\"ABCESEEEFS\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Max Increase to Keep City Skyline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "https://leetcode.com/problems/max-increase-to-keep-city-skyline/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c.\n",
    "\n",
    "A city's skyline is the the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.\n",
    "\n",
    "We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.\n",
    "\n",
    "Return the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def maxIncreaseKeepingSkyline(grid):\n",
    "    len_grid = len(grid)\n",
    "    max_in_rows = []\n",
    "    for i in grid:\n",
    "        max_in_rows.append(max(i))\n",
    "    max_in_columns = []\n",
    "    for i in list(zip(*grid)):\n",
    "        max_in_columns.append(max(i))\n",
    "    #print(max_in_rows, max_in_columns)\n",
    "    \n",
    "    total_increase = 0\n",
    "    for i in range(len_grid):\n",
    "        for j in range(len_grid):\n",
    "            if max_in_rows[i] <= max_in_columns[j]:\n",
    "                total_increase+=max_in_rows[i]-grid[i][j]\n",
    "            else:\n",
    "                 total_increase+=max_in_columns[j]-grid[i][j]\n",
    "    return total_increase"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "35"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxIncreaseKeepingSkyline(grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Interval List Intersections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "https://leetcode.com/problems/interval-list-intersections/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.\n",
    "\n",
    "Return the intersection of these two interval lists.\n",
    "\n",
    "A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.\n",
    "\n",
    "The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "## on ifs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def intervals_intersect(firstList, secondList):\n",
    "    i = 0\n",
    "    j = 0\n",
    "    \n",
    "    begin = None\n",
    "    end = None\n",
    "    \n",
    "    intersected = []\n",
    "    \n",
    "    \n",
    "    while (i <= len(firstList)-1) and (j <= len(secondList)-1):\n",
    "       # print(firstList[i], secondList[j])\n",
    "        if firstList[i][0] <  secondList[j][0]:\n",
    "            begin = secondList[j][0]\n",
    "            if firstList[i][1] < secondList[j][0]:\n",
    "                i+=1\n",
    "                begin = secondList[j][0]\n",
    "            elif (firstList[i][1] > secondList[j][0]) & (firstList[i][1] < secondList[j][1]):\n",
    "                end = firstList[i][1]\n",
    "                i+=1\n",
    "                intersected.append([begin, end])\n",
    "            elif (firstList[i][1] > secondList[j][0]) & (firstList[i][1] > secondList[j][1]):\n",
    "                end = secondList[j][1]\n",
    "                j+=1\n",
    "                intersected.append([begin, end])\n",
    "            elif firstList[i][1] == secondList[j][0]:\n",
    "                intersected.append([firstList[i][1], firstList[i][1]])\n",
    "                i+=1\n",
    "            elif secondList[j][1] == firstList[i][1]:\n",
    "                end = firstList[i][1]\n",
    "                intersected.append([begin, end])\n",
    "                j+=1\n",
    "                i+=1\n",
    "        elif secondList[j][0] <=  firstList[i][0]:\n",
    "            begin = firstList[i][0]\n",
    "            if secondList[j][1] < firstList[i][0]:\n",
    "                j+=1\n",
    "                begin = firstList[i][0]\n",
    "            elif (secondList[j][1] > firstList[i][0]) & (secondList[j][1] < firstList[i][1]):\n",
    "                end = secondList[j][1]\n",
    "                j+=1\n",
    "                intersected.append([begin, end])\n",
    "            elif (secondList[j][1] > firstList[i][0]) & (secondList[j][1] > firstList[i][1]):\n",
    "                end = firstList[i][1]\n",
    "                i+=1\n",
    "                intersected.append([begin, end])\n",
    "            elif secondList[j][1] == firstList[i][0]:\n",
    "                intersected.append([firstList[i][0], firstList[i][0]])\n",
    "                j+=1\n",
    "            elif secondList[j][1] == firstList[i][1]:\n",
    "                end = firstList[i][1]\n",
    "                intersected.append([begin, end])\n",
    "                j+=1\n",
    "                i+=1\n",
    "                \n",
    "    \n",
    "    return intersected                         "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "## min-max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def intervals_intersect(firstList, secondList):\n",
    "    i = 0\n",
    "    j = 0\n",
    "    \n",
    "    intersected = []\n",
    "    \n",
    "    while (i <= len(firstList)-1) and (j <= len(secondList)-1):\n",
    "        low = max(firstList[i][0], secondList[j][0])\n",
    "        high = min(firstList[i][1], secondList[j][1])\n",
    "        if low<=high:\n",
    "            intersected.append([low, high])\n",
    "            \n",
    "        if firstList[i][1] <= secondList[j][1]:\n",
    "            i+=1\n",
    "        else:\n",
    "            j+=1\n",
    "            \n",
    "    return intersected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "firstList = [[0,0], [0,2],[5,10],[13,23],[24,25]]\n",
    "secondList = [[1,5],[8,12],[15,24],[25,26]]\n",
    "intervals_intersect(firstList, secondList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Input: firstList = [[1,3],[5,9]]\n",
    "secondList = []\n",
    "\n",
    "intervals_intersect(firstList, secondList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[5, 10]]"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "firstList = [[5,10]]\n",
    "secondList = [[5,10]]\n",
    "\n",
    "intervals_intersect(firstList, secondList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[16, 16]]"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "firstList = [[14,16]]\n",
    "secondList = [[7,13],[16,20]]\n",
    "\n",
    "intervals_intersect(firstList, secondList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[8, 10], [12, 15]]"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "firstList = [[8,15]]\n",
    "secondList = [[2,6],[8,10],[12,20]]\n",
    "\n",
    "intervals_intersect(firstList, secondList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[4, 5], [9, 10], [11, 12], [14, 15], [16, 20]]"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "firstList = [[3,5],[9,20]]\n",
    "secondList = [[4,5],[7,10],[11,12],[14,15],[16,20]]\n",
    "intervals_intersect(firstList, secondList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, 3], [5, 6]]"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "firstList = [[0,3],[5,6],[14,18],[19,20]]\n",
    "secondList = [[3,8],[9,13]]\n",
    "\n",
    "intervals_intersect(firstList, secondList)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Number of Islands"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"1\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"1\",\"1\"]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"0\",\"0\"]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "grid = [[\"1\",\"1\",\"1\"],\n",
    "        [\"0\",\"1\",\"0\"],\n",
    "        [\"1\",\"1\",\"1\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def make_step(grid, i, j):\n",
    "    if j > len(grid[0])-1:\n",
    "        return False\n",
    "    if i > len(grid)-1:\n",
    "        return False\n",
    "    if j < 0:\n",
    "        return False\n",
    "    if i < 0:\n",
    "        return False\n",
    "    #print(i,j)\n",
    "    if grid[i][j] == \"1\":\n",
    "        grid[i][j] = \"-\"\n",
    "        possible_steps = [(i+1, j),(i-1, j), (i, j+1),  (i, j-1)]\n",
    "        for step in possible_steps:\n",
    "#             if step not in explored:\n",
    "#                 explored.append((step))\n",
    "            make_step(grid, step[0], step[1])\n",
    "    else:\n",
    "        grid[i][j] = \"-\"\n",
    "    \n",
    "   # return explored\n",
    "                    \n",
    "\n",
    "def numIslands(grid):\n",
    "    m = len(grid[0])\n",
    "    n = len(grid)\n",
    "    \n",
    "    #print(m, n)\n",
    "    \n",
    "   # explored = []\n",
    "    \n",
    "    islands = 0\n",
    "\n",
    "    for row in range(n):\n",
    "        for col in range(m):\n",
    "            #print(explored)\n",
    "#             if (row, col) not in explored:\n",
    "#                 #print('row, col',row, col)\n",
    "#                 explored.append((row, col))\n",
    "#                 #print(row, col)\n",
    "                if grid[row][col] == \"1\":\n",
    "                    make_step(grid, row, col)\n",
    "                    islands+=1\n",
    "                    \n",
    "    return islands\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 233,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# House Robber (DP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/house-robber/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.\n",
    "\n",
    "Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: nums = [1,2,3,1]  \n",
    "Output: 4  \n",
    "Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).  \n",
    "Total amount you can rob = 1 + 3 = 4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Top-Down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 237,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 237,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def rob(nums):\n",
    "    def dp(i):\n",
    "        if i == 0:\n",
    "            return nums[0]\n",
    "        \n",
    "        if i == 1:\n",
    "            return max(nums[0], nums[1])\n",
    "        \n",
    "        if i not in memo:\n",
    "            memo[i] = max(dp(i-1), dp(i-2) + nums[i])\n",
    "            \n",
    "        return memo[i]\n",
    "\n",
    "    memo = {}\n",
    "    \n",
    "    return dp(len(nums)-1)\n",
    "\n",
    "rob([1, 2, 3, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bottom-Up"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "for i in range(2, 4):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rob(nums):\n",
    "    n = len(nums)\n",
    "    \n",
    "    if n == 1:\n",
    "        return nums[0]\n",
    "    memo =[-1] * n\n",
    "    \n",
    "    memo[0] = nums[0]  \n",
    "\n",
    "    memo[1] = max(nums[0], nums[1])\n",
    "    \n",
    "    for i in range(2, n):\n",
    "        memo[i] = max(memo[i-1], memo[i-2]+nums[i])\n",
    "    \n",
    "    return memo[len(nums)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 255,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rob([1, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Permutation in String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/permutation-in-string/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "s1 = \"ab\", s2 = \"eidbaooo\"  \n",
    "Output: true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [],
   "source": [
    "def checkInclusion(s1: str, s2: str):\n",
    "    dicts1 = {}\n",
    "    for s in s1:\n",
    "        if s in dicts1:\n",
    "            dicts1[s]+=1\n",
    "        else:\n",
    "            dicts1[s]=1\n",
    "    \n",
    "    i = 0\n",
    "    j = len(s2)\n",
    "    \n",
    "    while i <= j-len(s1):\n",
    "        dicts2 = {}\n",
    "        for letter in s2[i:i+len(s1)]:\n",
    "            if letter in dicts2:\n",
    "                dicts2[letter]+=1\n",
    "            elif letter in dicts1:\n",
    "                dicts2[letter]=1\n",
    "#             else:\n",
    "#                 i+=1\n",
    "#                 break\n",
    "        #print(i, j, dicts1, dicts2)\n",
    "        if dicts2==dicts1:\n",
    "            return True\n",
    "        \n",
    "        i+=1\n",
    "        \n",
    "    return False\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Rotting Oranges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/rotting-oranges/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given an m x n grid where each cell can have one of three values:\n",
    "\n",
    "0 representing an empty cell,  \n",
    "1 representing a fresh orange, or  \n",
    "2 representing a rotten orange.  \n",
    "Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.  \n",
    "\n",
    "Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: grid = [[2,1,1],[1,1,0],[0,1,1]]  \n",
    "Output: 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 331,
   "metadata": {},
   "outputs": [],
   "source": [
    "def orangesRotting(grid):   \n",
    "    \n",
    "    def make_step(grid, time):\n",
    "        cnt_applicable = False\n",
    "\n",
    "        for i in range(0, len(grid)):\n",
    "            for j in range(0, len(grid[0])):\n",
    "                #print(i,j)\n",
    "                if grid[i][j] == time:\n",
    "                    #print(i, j)\n",
    "                    possible_steps = [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]\n",
    "\n",
    "                    for step in possible_steps:\n",
    "                        #print(step)\n",
    "                        if (step[0] < len(grid)) & (step[0] >=0) :\n",
    "                            if (step[1] < len(grid[0])) & (step[1]>=0):\n",
    "                                if grid[step[0]][step[1]] == 1:\n",
    "                                    grid[step[0]][step[1]] = time+1\n",
    "\n",
    "                                    cnt_applicable = True\n",
    "\n",
    "        return cnt_applicable\n",
    "    \n",
    "    time = 2\n",
    "    while make_step(grid, time):\n",
    "        time+=1\n",
    "        #print(grid)\n",
    "\n",
    "\n",
    "    for x in grid:\n",
    "        if 1 in x:\n",
    "            return -1\n",
    "\n",
    "    return time-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 325,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 325,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[2,1,1],[1,1,0],[0,1,1]]\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 327,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 327,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[2,1,1],[0,1,1],[1,0,1]]\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 328,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 328,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[0,2]]\n",
    "\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 329,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 329,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[2],[1]]\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: nums = [1,2,3]  \n",
    "\n",
    "Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 369,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 369,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 380,
   "metadata": {},
   "outputs": [],
   "source": [
    "def permute(nums):\n",
    "    def backtrack(first = 0):\n",
    "        \n",
    "        if first == len(nums):\n",
    "            output.append(nums.copy())\n",
    "        \n",
    "        for n in range(first, len(nums)):\n",
    "            nums[first], nums[n] = nums[n], nums[first]\n",
    "            \n",
    "            backtrack(first+1)\n",
    "            \n",
    "            nums[first], nums[n] = nums[n], nums[first]\n",
    "            #print(first, n, nums)\n",
    "              \n",
    "    \n",
    "    output = []\n",
    "    \n",
    "    backtrack()\n",
    "    \n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 381,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]"
      ]
     },
     "execution_count": 381,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3]\n",
    "permute(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generate Parentheses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 447,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, [4, 5, 6]]\n",
      "[1, 2, 3, [4, 5, 6], 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "# a = [1, 2, 3]\n",
    "# b = [4, 5, 6]\n",
    "\n",
    "# a.append(b)\n",
    "# print(a)\n",
    "\n",
    "# a.extend(b)\n",
    "# print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 461,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 2, 5]"
      ]
     },
     "execution_count": 461,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# d = {4:2, 2:4, 5:8}\n",
    "\n",
    "# sorted(d, key = d.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 439,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['(())', '()()']"
      ]
     },
     "execution_count": 439,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def generateParenthesis(n: int):\n",
    "    \n",
    "    total_length = n*2\n",
    "    \n",
    "    parenthesis_list = []\n",
    "    \n",
    "    def backtrack(left = 0, right = 0, S = []):\n",
    "        if len(S) == total_length:   \n",
    "            parenthesis_list.append(\"\".join(S))\n",
    "            return\n",
    "            \n",
    "        if left < n:\n",
    "            S.append(\"(\")\n",
    "            backtrack(left+1, right, S )\n",
    "            S.pop()\n",
    "\n",
    "        if right < left:\n",
    "            S.append(\")\")\n",
    "            backtrack(left, right+1, S )\n",
    "            S.pop()\n",
    "    \n",
    "    backtrack()\n",
    "            \n",
    "            \n",
    "    return parenthesis_list\n",
    "            \n",
    "    \n",
    "            \n",
    "            \n",
    "generateParenthesis(2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Max Consecutive Ones II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/max-consecutive-ones-ii/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 411,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 411,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,0,1,1,0]\n",
    "\n",
    "def findMaxConsequtiveOnes(nums):\n",
    "    i = 0\n",
    "    j = 0\n",
    "    \n",
    "    zero_index = -1\n",
    "    \n",
    "    max_length = []\n",
    "    \n",
    "    while j != len(nums):\n",
    "        for it in range(i, len(nums)):\n",
    "            if nums[it] == 1:\n",
    "                j+=1\n",
    "            elif (nums[it] == 0) & (zero_index == -1):\n",
    "                zero_index = it  \n",
    "                j+=1\n",
    "            else:\n",
    "                #print(it,i,j, zero_index)\n",
    "                max_length.append(j-i)\n",
    "                i = zero_index+1\n",
    "                j = zero_index+1\n",
    "                zero_index = -1\n",
    "                #print(it,i,j, zero_index)\n",
    "                break\n",
    "                \n",
    "    \n",
    "    max_length.append(j-i)        \n",
    "            \n",
    "    return max(max_length)\n",
    "\n",
    "findMaxConsequtiveOnes([1,0,1,1,0,1, 1, 1, 0, 1])\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Longest Common Subsequence (not done)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 275,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 275,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " def longestCommonSubsequence( text1, text2):\n",
    "        \n",
    "        def memo_solve(p1, p2):\n",
    "            \n",
    "            # Base case: If either string is now empty, we can't match\n",
    "            # up anymore characters.\n",
    "            if p1 == len(text1) or p2 == len(text2):\n",
    "                return 0\n",
    "            \n",
    "            # Option 1: We don't include text1[p1] in the solution.\n",
    "            option_1 = memo_solve(p1 + 1, p2)\n",
    "            \n",
    "            # Option 2: We include text1[p1] in the solution, as long as\n",
    "            # a match for it in text2 at or after p2 exists.\n",
    "            first_occurence = text2.find(text1[p1], p2)\n",
    "            option_2 = 0\n",
    "            if first_occurence != -1:\n",
    "                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n",
    "            \n",
    "            # Return the best option.\n",
    "            return max(option_1, option_2)\n",
    "                \n",
    "        return memo_solve(0, 0)\n",
    "    \n",
    "longestCommonSubsequence('abcde', 'ace')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rotate Array (not done)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: nums = [-1,-100,3,99], k = 2\n",
    "    \n",
    "Output: [3,99,-1,-100]\n",
    "    \n",
    "Explanation:   \n",
    "rotate 1 steps to the right: [99,-1,-100,3]  \n",
    "rotate 2 steps to the right: [3,99,-1,-100]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 258,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3]"
      ]
     },
     "execution_count": 258,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tst = [1, 2, 3]\n",
    "tst.pop(0)\n",
    "tst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 273,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 273,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3%3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotate(nums, k):\n",
    "    val_to_remember = []\n",
    "    i_to_skip = []\n",
    "    for i in range(len(nums)+1):\n",
    "        if i not in i_to_skip:\n",
    "            val_to_remember.append(i+k)\n",
    "            i_to_skip.append(i+k) \n",
    "            nums[i+k] = nums[i]\n",
    "            \n",
    "    \n",
    "    return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotate(nums, k):\n",
    "    n = len(nums)\n",
    "    k %= n\n",
    "\n",
    "    start = count = 0\n",
    "    while count < n:\n",
    "        current, prev = start, nums[start]\n",
    "        while True:\n",
    "            next_idx = (current + k) % n\n",
    "            nums[next_idx], prev = prev, nums[next_idx]\n",
    "            current = next_idx\n",
    "            count += 1\n",
    "\n",
    "            if start == current:\n",
    "                break\n",
    "        start += 1\n",
    "rotate([1, 2, 3, 4, 5, 6], 2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Character replacement (not done)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 731,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 731,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def characterReplacement(s: str, k: int) :\n",
    "    d={}\n",
    "    previous = s[0]\n",
    "    possible_longest = []\n",
    "    #cnt = 0\n",
    "    for i in s:\n",
    "        if i not in d:\n",
    "            d[i] = [0,k,False]\n",
    "            #cnt = 0\n",
    "        if (i!= previous):\n",
    "            d[i][0]+=1\n",
    "            if (d[i][1] > 0)& (d[i][0]==1):\n",
    "                d[i][0]+=1\n",
    "                d[i][1]-=1 \n",
    "                d[i][2]=True\n",
    "            elif (d[i][2]==True) & (d[i][1] == 0):\n",
    "                possible_longest.append(d[i][0])   \n",
    "                d[i][0]-=1\n",
    "                d[i][1]+=1\n",
    "            if d[previous][1] == 0:\n",
    "                possible_longest.append(d[previous][0])      \n",
    "                d[previous] = [0,k, False]  \n",
    "            if d[previous][1] != 0:\n",
    "                d[previous][1]-=1\n",
    "                d[previous][0]+=1\n",
    "                if d[previous][1] == 0:\n",
    "                    possible_longest.append(d[previous][0])                    \n",
    "        elif (i== previous):\n",
    "            d[i][0]+=1\n",
    "        #cnt+=1\n",
    "        #print(i, previous)\n",
    "        previous = i\n",
    "    possible_longest=possible_longest+[k[0] for k in d.values()]\n",
    "    #print(d)\n",
    "    return(max(possible_longest))\n",
    "\n",
    "characterReplacement(\n",
    "    s = \"KRSCDCSONAJNH\"\n",
    ", k = 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 720,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "d = {'K': [2, 3, False], 'R': [3, 2, True], 'S': [5, 1, True], 'C': [5, 1, True], 'D': [3, 2, True], 'O': [3, 2, True], 'N': [5, 1, True], 'A': [3, 2, True], 'J': [3, 2, True], 'H': [2, 3, True]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 728,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 5, 3, 3, 5, 3, 3, 2]"
      ]
     },
     "execution_count": 728,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[k[0] for k in d.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 579,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 579,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "characterReplacement(\n",
    "    s = \"KRSCDCSONAJNHLBMDQGIFCPEKPOHQIHLTDIQGEKLRLCQNBOHNDQGHJPNDQPERNFSSSRDEQLFPCCCARFMDLHADJADAGNNSBNCJQOF\"\n",
    ", k = 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 591,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 591,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 694,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'KRSCD'"
      ]
     },
     "execution_count": 694,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"KRSCDCSON\"\n",
    "s[:-4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 703,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A\n",
      "BAA\n",
      "{'A': 5} []\n",
      "B\n",
      "AA\n",
      "{'A': 5, 'B': 3} [5]\n",
      "A\n",
      "A\n",
      "{'A': 4, 'B': 3} [5, 3]\n",
      "A\n",
      "\n",
      "{'A': 3, 'B': 3} [5, 3, 4]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 703,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def characterReplacement(s: str, k: int):\n",
    "    d={}\n",
    "    max_possible_length = []\n",
    "    cnt_i = 1\n",
    "    cnt_j = k+2\n",
    "    cnt_local = 0\n",
    "    cur_cnt = 0\n",
    "    #print(cnt_j)\n",
    "    for i in s:\n",
    "        print(i)\n",
    "        cnt_local = s[cnt_i:cnt_j].count(i)\n",
    "        print(s[cnt_i:cnt_j])\n",
    "#         print(cnt_local)\n",
    "        cnt_j+=cnt_local\n",
    "        while cur_cnt < cnt_local:\n",
    "            cur_cnt=cnt_local\n",
    "#             print(s[cnt_i:cnt_j])\n",
    "            cnt_local = s[cnt_i:cnt_j].count(i)\n",
    "            cnt_j+=1\n",
    "        if cnt_local == len(s)-1:\n",
    "            d[i] = cnt_local+1\n",
    "            max_possible_length.append(d[i])\n",
    "            break\n",
    "        else:\n",
    "       # print(cnt_local)\n",
    "            d[i] = cnt_local+k+1\n",
    "        print(d,max_possible_length)\n",
    "        max_possible_length.append(d[i])\n",
    "#            d[i] = 0\n",
    "        cnt_i+=1\n",
    "        cnt_j=k+2+cnt_i\n",
    "\n",
    "    return max(max_possible_length)\n",
    "\n",
    "characterReplacement(\n",
    "    \"ABAA\", \n",
    "    2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 623,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 623,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"KRSCDCSON\".count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 624,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "K\n",
      "{'K': 5}\n",
      "R\n",
      "{'K': 5, 'R': 5}\n",
      "S\n",
      "{'K': 5, 'R': 5, 'S': 5}\n",
      "C\n",
      "{'K': 5, 'R': 5, 'S': 5, 'C': 5}\n",
      "D\n",
      "{'K': 5, 'R': 5, 'S': 5, 'C': 5, 'D': 4}\n",
      "C\n",
      "{'K': 5, 'R': 5, 'S': 5, 'C': 4, 'D': 4}\n",
      "S\n",
      "{'K': 5, 'R': 5, 'S': 4, 'C': 4, 'D': 4}\n",
      "O\n",
      "{'K': 5, 'R': 5, 'S': 4, 'C': 4, 'D': 4, 'O': 4}\n",
      "N\n",
      "{'K': 5, 'R': 5, 'S': 4, 'C': 4, 'D': 4, 'O': 4, 'N': 4}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'K': 5, 'R': 5, 'S': 4, 'C': 4, 'D': 4, 'O': 4, 'N': 4}"
      ]
     },
     "execution_count": 624,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "characterReplacement(\"KRSCDCSON\", 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 772,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 772,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def maxArea(height):    \n",
    "    dist = len(height)-1\n",
    "    i = 0\n",
    "    j = -1\n",
    "    max_area=0\n",
    "    \n",
    "    while dist > 0:\n",
    "        l = height[i]\n",
    "        r = height[j]\n",
    "        if l < r:\n",
    "            max_area = max(max_area, l * dist)\n",
    "            i+=1\n",
    "        else:\n",
    "            max_area = max(max_area, r * dist)\n",
    "            j-=1\n",
    "        dist-=1    \n",
    "    return max_area\n",
    "maxArea([2,3,4,5,18,17,6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 750,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 750,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxArea([1,8,6,2,5,4,8,3,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 732,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "height = [1,8,6,2,5,4,8,3,7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 735,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 735,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "height[-2]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}