<jupyter_start><jupyter_text>Dynamic Programming & Programming **Grid Traveller****O(n+m)**<jupyter_code>def grid_traveller(m,n, dict_={}):
    key = (m,n)
    if key in dict_:
        return dict_[key]
    if (m == 0 or n == 0) :
        return 0
    if (m == 1 and n == 1) :
        return 1
    dict_[key] = grid_traveller(m-1,n,dict_) + grid_traveller(m,n-1, dict_)
    return dict_[key]
grid_traveller(2,3), grid_traveller(1,1), grid_traveller(3,2), grid_traveller(18,18)<jupyter_output><empty_output><jupyter_text>**Fibonacci****O(n)**<jupyter_code>def fib(n, dict_ = {}):
    if n<=2:
        return 1
    if n in dict_:
        return dict_[n]
    dict_[n] = fib(n-1, dict_) + fib(n-2, dict_)
    return dict_[n]
%%timeit
fib(150)
def fib_ls(n):
    fib_arr = [0,1]

    for i in range(2, n+1):
        fib_arr.append(fib_arr[i-1]+fib_arr[i-2])
    return fib_arr[n]
%%timeit
fib_ls(150)<jupyter_output>40.7 µs ± 1.06 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)<jupyter_text>**Generating n-grams**<jupyter_code>s = "The quick brown fox jumped over the lazy dog.".split()
n = 4
n_grams = list(zip(*[s[i:] for i in range(n)]))
n_grams<jupyter_output><empty_output><jupyter_text>**Group Anagrams****`O(m*n)`**, where **`m`** = number of strings and **`n`** = number of characters in a stringGiven an array of strings strs, group the anagrams together. You can return the answer in any order.An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.**Solved using hashmap** Example 1:Input: strs = ["eat","tea","tan","ate","nat","bat"]Output: [["bat"],["nat","tan"],["ate","eat","tea"]]Example 2:Input: strs = [""]Output: [[""]]Example 3:Input: strs = ["a"]Output: [["a"]]<jupyter_code>from typing import List
# from collections import defaultdict

def groupAnagrams(strs: List[str]) -> List[List[str]]:
        
        # results = defaultdict(list)
        results = {}
        
        for each_str in strs:
            count = [0] * 26
            
            for each_char in each_str:
                count[ord(each_char) - ord('a')] +=1
                
            results.setdefault(tuple(count), []).append(each_str)
            # results[tuple(count)].append(each_str)
            
        return results.values()
strs = ["eat","tea","tan","ate","nat","bat"]
groupAnagrams(strs=strs)<jupyter_output><empty_output><jupyter_text>**Can Sum****O(m*n)**<jupyter_code>def can_sum(target_sum,ls: list, memo:dict):
    if target_sum in memo:
        return memo[target_sum]
    if target_sum==0:
        return True
    if target_sum < 0:
        return False
    
    for i in ls:
        remainder = target_sum - i
        if can_sum(remainder, ls, memo):
            memo[target_sum] = True
            return True
    
    memo[target_sum]=False
    return False
can_sum(7, [5,4,3,7], {}), can_sum(7, [2,3], {}), can_sum(7, [2,4], {}), can_sum(8, [2,3,5], {}), can_sum(300, [7,14], {}), can_sum(0,[1,2,3], {})<jupyter_output><empty_output><jupyter_text>**Two Sum****O(n)**Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order.**Solved using hashmap** Example 1:Input: nums = [2,7,11,15], target = 9Output: [0,1]Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].Example 2:Input: nums = [3,2,4], target = 6Output: [1,2]Example 3:Input: nums = [3,3], target = 6Output: [0,1]<jupyter_code>from typing import List

def twoSum(nums: List[int], target: int) -> List[int]:
        memo = {}
        
        for idx, num in enumerate(nums):
            diff = target - num
            if diff in memo:
                return [memo[diff], idx]
            memo[num] = idx
nums = [2,7,11,15]
target = 9
twoSum(nums,target)<jupyter_output><empty_output><jupyter_text>**Valid Anagram****O(nlogn)**Given two strings s and t, return true if t is an anagram of s, and false otherwise.An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.**Solved using sorted list/just sorting the strings alphabetically** Example 1:Input: s = "anagram", t = "nagaram"Output: trueExample 2:Input: s = "rat", t = "car"Output: false<jupyter_code>def isAnagram(s: str, t: str) -> bool:
        return sorted(s) == sorted(t)
        s = list(s)
        s.sort()
        t = list(t)
        t.sort()
        if s == t:
            return True
        return False
s = "anagram"
t = "nagaram"
isAnagram(s,t)<jupyter_output><empty_output><jupyter_text>**Pivot Index**Given an array of integers nums, calculate the pivot index of this array.The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.Return the leftmost pivot index. If no such index exists, return -1.<jupyter_code>from typing import List

def pivotIndex(nums: List[int]) -> int:
        tot_sum = sum(nums)
        for idx,_ in enumerate(nums):
            if not idx:
                l_sum = 0
                r_sum = tot_sum - nums[idx]
                if l_sum == r_sum:
                    return idx
            elif idx:
                l_sum = sum(nums[:idx])
                r_sum = tot_sum -nums[idx]- l_sum
                if l_sum == r_sum:
                    return idx
        return -1
nums = [1,7,3,6,5,6]
pivotIndex(nums)<jupyter_output><empty_output><jupyter_text>**Top K Frequent Elements****O(n)**Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Example 1:Input: nums = [1,1,1,2,2,3], k = 2Output: [1,2]Example 2:Input: nums = [1], k = 1Output: [1]<jupyter_code>from typing import List

def topKFrequent(nums: List[int], k: int) -> List[int]:
        
        memo = {}
        val_list = [[] for i in range(len(nums) + 1)]
        
        for num in nums:
            memo[num] = 1 + memo.get(num, 0)
            
        for key, val in memo.items():
            val_list[val].append(key)
        
        results = []
        for i in range(len(val_list)-1, 0, -1):
            for num in val_list[i]:
                results.append(num)
                if len(results) == k:
                    return results
        
nums = [1,1,1,2,2,3]
k = 2
topKFrequent(nums, k)<jupyter_output><empty_output><jupyter_text>**Two Sum II - Input Array Is Sorted****O(n)**Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.Your solution must use only constant extra space.**Solved with two pointers** Example 1:Input: numbers = [2,7,11,15], target = 9Output: [1,2]Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].Example 2:Input: numbers = [2,3,4], target = 6Output: [1,3]Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].Example 3:Input: numbers = [-1,0], target = -1Output: [1,2]Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].<jupyter_code>from typing import List

def twoSum(numbers: List[int], target: int) -> List[int]:
        l_idx , r_idx = 0, len(numbers) - 1
        while l_idx < r_idx:
            cur_sum = numbers[l_idx] + numbers[r_idx]
            if cur_sum > target:
                r_idx -= 1
            elif cur_sum < target:
                l_idx += 1
            else:
                return [l_idx+1, r_idx+1]
numbers = [2,7,11,15]
target = 9
twoSum(numbers, target)<jupyter_output><empty_output><jupyter_text>**ThreeSum****O(n^2)**Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.Notice that the solution set must not contain duplicate triplets.**Solved with three pointers** Example 1:Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]Example 2:Input: nums = []Output: []Example 3:Input: nums = [0]Output: []<jupyter_code>from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
        nums.sort()
        results = []
        
        for i,j in enumerate(nums):
            if i > 0 and j==nums[i-1]:
                continue # we want to skip duplicates 
                # in the first position as it will avoid duplicate triplets
            
            l_idx, r_idx = i+1, len(nums) -1
            while l_idx < r_idx:
                three_sum = j + nums[l_idx] + nums[r_idx] # inside the two pointer loop as the first pointer is fixed
                
                if three_sum > 0:
                    r_idx -= 1
                elif three_sum < 0:
                    l_idx += 1
                else:
                    results.append([j, nums[l_idx], nums[r_idx]])
                    # only one pointer needs to be shifted since 
                    # the above loop takes care when the three_sum is either < or > 0
                    l_idx +=1
                    while nums[l_idx] == nums[l_idx-1] and l_idx < r_idx:
                        l_idx +=1
        return results
                    
nums = [-1,0,1,2,-1,-4]
threeSum(nums)<jupyter_output><empty_output><jupyter_text>**Binary Search for a sorted list**Find the if the number exists in a list<jupyter_code>def binary_search(arr, low, high, number):
    mid = (high+low)//2
    if high >= low:
        if arr[mid] < number:
            return binary_search(arr,mid+1,high, number)
        elif arr[mid] > number:
            return binary_search(arr, low, mid-1, number)
        else:
            return mid
    else:
        return -1
def binary_search(arr, low, high, number):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == number:
           return mid
        elif arr[mid] > number:
           return binary_search(arr, low, mid-1, number)
        else:
           return binary_search(arr, mid+1, high, number)
    else:
        return -1
arr = [5, 12, 17, 19, 22, 30, 78, 900]
number = 22
binary_search(arr, 0, len(arr)-1, number)<jupyter_output><empty_output><jupyter_text>**Valid Parentheses****O(n)**Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.An input string is valid if:Open brackets must be closed by the same type of brackets.Open brackets must be closed in the correct order.**Solved using a stack** Example 1:Input: s = "()"Output: trueExample 2:Input: s = "()[]{}"Output: trueExample 3:Input: s = "(]"Output: false<jupyter_code>def isValid(s: str) -> bool:
    stack = []
    par_mapping = {
        ')':'(',
        ']':'[',
        '}':'{'
    }
    
    for char in s:
        if char in par_mapping:
            if stack and stack[-1] == par_mapping[char]: # if stack not empty and the last element
                # of the stack is == to the char in question; as the last element of a stack
                # is the first one added
                stack.pop()
            else:
                return False
            
        else:
            stack.append(char)
            
    return True if not stack else False
s='())('
isValid(s)<jupyter_output><empty_output><jupyter_text>**Plus One** **O(n)**You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.Increment the large integer by one and return the resulting array of digits. Example 1:Input: digits = [1,2,3]Output: [1,2,4]Explanation: The array represents the integer 123.Incrementing by one gives 123 + 1 = 124.Thus, the result should be [1,2,4].Example 2:Input: digits = [4,3,2,1]Output: [4,3,2,2]Explanation: The array represents the integer 4321.Incrementing by one gives 4321 + 1 = 4322.Thus, the result should be [4,3,2,2].Example 3:Input: digits = [9]Output: [1,0]Explanation: The array represents the integer 9.Incrementing by one gives 9 + 1 = 10.Thus, the result should be [1,0].<jupyter_code>from typing import List

def plusOne(digits: List[int]) -> List[int]:
        dig_len = len(digits) -1
        while digits[dig_len]==9:
            digits[dig_len] = 0
            dig_len-=1
        if dig_len < 0:
            digits = [1] + digits
        else:
            digits[dig_len] = digits[dig_len] + 1
        return digits
digits = [9]
plusOne(digits)<jupyter_output><empty_output><jupyter_text>**Min Stack**Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.Implement the MinStack class:* MinStack() initializes the stack object.* void push(int val) pushes the element val onto the stack.* void pop() removes the element on the top of the stack.* int top() gets the top element of the stack.* int getMin() retrieves the minimum element in the stack. Example 1:Input["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]Output[null,null,null,null,-3,null,0,-2]Explanation* MinStack minStack = new MinStack();* minStack.push(-2);* minStack.push(0);* minStack.push(-3);* minStack.getMin(); // return -3* minStack.pop();* minStack.top();    // return 0* minStack.getMin(); // return -2  **Solution**To be able to find out the min of the stack at **O(1)**, one has to calculate the min every time there's an element added. This is best done if there is a separate minimum list, where the minimum is calculated every time that an element is added to the original stack and if an element is removed from the same stack then it must be remmoved from the minimum list too.<jupyter_code>class MinStack:

    def __init__(self):
        self.minstack = []
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        min_val = min(val,self.minstack[-1] if self.minstack else val)
        self.minstack.append(min_val)
        

    def pop(self) -> None:
        self.minstack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()<jupyter_output><empty_output><jupyter_text>**Contains Duplicate****O(n)**Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. Example 1:Input: nums = [1,2,3,1]Output: trueExample 2:Input: nums = [1,2,3,4]Output: falseExample 3:Input: nums = [1,1,1,3,3,4,3,2,4,2]Output: true<jupyter_code>from typing import List

def containsDuplicate(nums: List[int]) -> bool:
    # O(nlogn)

    # counts = {}
    
    # for i in nums:
    #     counts[i] = 1 + counts.get(i,0)
    # vals = list(counts.values())
    # vals.sort(reverse=True)
    # if vals[0] > 1:
    #     return True
    # else:
    #     return False
    temp = {}
    for i,num in enumerate(nums):
        if num in temp:
            return True
        temp[num] = i
    return False
nums = [1,2,3,1]
containsDuplicate(nums)<jupyter_output><empty_output><jupyter_text>**Contains Duplicate II****O(n)**Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k. Example 1:Input: nums = [1,2,3,1], k = 3Output: trueExample 2:Input: nums = [1,0,1,1], k = 1Output: trueExample 3:Input: nums = [1,2,3,1,2,3], k = 2Output: false<jupyter_code>from typing import List

def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    
    
    memo = {}
    for i,j in enumerate(nums):
        if j in memo and abs(memo[j] - i)<=k:
            return True
        memo[j] = i
    return False
nums = [1,2,3,1]
k = 3
containsNearbyDuplicate(nums,k)<jupyter_output><empty_output><jupyter_text>**Longest Consecutive Sequence****O(n)**Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.You must write an algorithm that runs in O(n) time.**Solved by set.** Example 1:Input: nums = [100,4,200,1,3,2]Output: 4Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.Example 2:Input: nums = [0,3,7,2,5,8,4,6,0,1]Output: 9<jupyter_code># nlog(n) solution
from typing import List

def longestConsecutive(nums: List[int]) -> int:
    if not nums:
        return 0
    nums.sort()
    consec = 1
    count = 1
    for i,j in enumerate(nums):
        if i==0:
            continue
        if i>0 and nums[i]==nums[i-1]:
            continue
        if j == nums[i-1]+1:
            consec +=1
        else:
            if count < consec:
                count = consec
                consec = 1
            else:
                consec = 1
    return count if count>consec else consec
#                 [0,0,1,2,3,4,5]
#                 [0, 2,3,4, 10,13,14,]
#                 [1,2,7,8,10,11,12,13]
# O(n) solution
from typing import List

def longestConsecutive(nums: List[int]) -> int:
    nums_set = set(nums)
    longest = 0
    for n in nums:
        if n-1 not in nums_set:
            # the idea is to find for each number if there is a number to it's left, which 
            # means that if there is one that means that this number isn't the beginning of the 
            # sequence of numbers but rather somewhere in the sequence
            # e.g. [1,2,3,4,100,200], for 1 there is no number (n-1) preceeding it therefore
            # it's a beginning of a valid sequence, however, for 2 there is as it's 1
            # once a valid sequence is found increase the counter as long as you find the 
            # numbers in the list
            length = 0
            while length+n in nums_set:
                length +=1
            longest = max(length, longest)
    return longest
#                 [0,0,1,2,3,4,5]
#                 [0, 2,3,4, 10,13,14,]
#                 [1,2,7,8,10,11,12,13]
nums = [0,3,7,2,5,8,4,6,0,1]
longestConsecutive(nums)<jupyter_output><empty_output><jupyter_text>**Best Time to Buy and Sell Stock****O(n)**You are given an array prices where prices[i] is the price of a given stock on the ith day.You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.**Solved by creating a window with two pointers.** Example 1:Input: prices = [7,1,5,3,6,4]Output: 5Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.Example 2:Input: prices = [7,6,4,3,1]Output: 0Explanation: In this case, no transactions are done and the max profit = 0.<jupyter_code>from typing import List

def maxProfit(prices: List[int]) -> int:
    l_idx, r_idx = 0,1
    profit = 0
    while r_idx < len(prices): # if len(prices)-1 instead of len(prices)then 
        # r_idx would not go till the last element
        if prices[l_idx] < prices[r_idx]:
            profit = max(profit, prices[r_idx] - prices[l_idx])
        else:
            l_idx = r_idx
            # this is needed because the pointer has to go to
            # the lowest value, pointing to right pointer, which might not be adjacent and therefore
            # cannot be incremented by + 1
            # e.g. [7, 2, 3, 4, 5, 1, 9] in this case if we do l_idx +=1 we would never reach 1 as the lowest value
            # and it would be stuck at 3
        r_idx +=1
    return profit
prices = [1,2,4,2,5,7,2,4,9,0,9]
maxProfit(prices)
from typing import List

def maxProfit(prices: List[int]) -> int:
    l_idx, r_idx = 0,1
    profit = 0
    while r_idx < len(prices): # if len(prices) instead of len(prices)-1 then 
        # r_idx would not go till the last element
        if prices[l_idx] > prices[r_idx]:
            # this is needed because the pointer has to go to
            # the lowest value, pointing to right pointer, which might not be adjacent and therefore
            # cannot be incremented by + 1
            # e.g. [7, 2, 3, 4, 5, 1, 9] in this case if we do l_idx +=1 we would never reach 1 as the lowest value
            # and it would be stuck at 3
            l_idx = r_idx
        else:
            profit = max(profit, prices[r_idx] - prices[l_idx])
        r_idx +=1
    return profit
prices = [1,2,4,2,5,7,2,4,9,0,9]
maxProfit(prices)<jupyter_output><empty_output><jupyter_text>**Longest Substring Without Repeating Characters****O(n)**Given a string s, find the length of the longest substring without repeating characters.**Solved by creating a window with two pointers.** Example 1:Input: s = "abcabcbb"Output: 3Explanation: The answer is "abc", with the length of 3.Example 2:Input: s = "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.Example 3:Input: s = "pwwkew"Output: 3Explanation: The answer is "wke", with the length of 3.Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. To retrieve the longest consecutive substring, we keep adding each letter of the string to an list as long as we don't encounter a duplicate, once we do encounter a duplicate, we drop all the letters from the start of the substring until the duplicate is removed and update the start of the substring each time we are dropping a letter from the beginning of the substring. Once we have a substring with unique letters, we count the length of the substring.For instance: "abcabcbb" we keep adding the first substring "abc" and then the next letter is "a" which is a duplicate so we drop the first letter of the substring "a" and then move ahead. At a point we get "abcb", in this case we drop the first two letters"ab" and we have the substring "cb".<jupyter_code>def lengthOfLongestSubstring(s: str) -> int:
    substr = []
    l_idx = 0
    length = 0
    for r_idx in range(len(s)):
        while s[r_idx] in substr:
            substr.remove(s[l_idx])
            l_idx +=1
        substr.append(s[r_idx])
        length = max(length, (r_idx - l_idx)+1)
    return length
def lengthOfLongestSubstring(s: str) -> int:
    substr = set()
    l_idx = 0
    length = 0
    for r_idx in range(len(s)):
        while s[r_idx] in substr:
            substr.remove(s[l_idx])
            l_idx +=1
        substr.add(s[r_idx])
        length = max(length, (r_idx - l_idx)+1)

    return length
s1 = "abcabcbb"
s2 = "bbbbb"
s3 = "pwwkew"
lengthOfLongestSubstring(s1),lengthOfLongestSubstring(s2),lengthOfLongestSubstring(s3)<jupyter_output><empty_output><jupyter_text>**Longest Repeating Character Replacement****O(n)**You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.Return the length of the longest substring containing the same letter you can get after performing the above operations.**Solved using two pointers.** Input: s = "ABAB", k = 2Output: 4Explanation: Replace the two 'A's with two 'B's or vice versa.Example 2:Input: s = "AABABBA", k = 1Output: 4Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".The substring "BBBB" has the longest repeating letters, which is 4. In a given window formed by a left and right index, if we take the count of the maximum occurring letters and substract it from the length of the window then we will know exactly how many replacements we have to make to get a substring filled with duplicates. For instance, "ABAB", window length = 4, maximum occurring letters are "A" & "B" each occuring 2 times, and we can perform replacement 2 times, then 4-2 = 2 and we can replace each of the "A" & "B" since we are allowed 2 operations, which translates the maximum length of the substring being 4. However, if the window length - maximum occuring letters > number of replacement operations, then we need to move the left index by one and substract it's corresponding count.<jupyter_code>def characterReplacement(s: str, k: int) -> int:
        length = 0
        l_idx = 0
        counts = {}
        for r_idx in range(len(s)):
            counts[s[r_idx]] = 1 + counts.get(s[r_idx],0)
            if (r_idx - l_idx)+1 - max(counts.values()) <=k:
                length = max(length, (r_idx - l_idx)+1)
            else:
                counts[s[l_idx]] -=1
                l_idx +=1
        return length

s = "AABABBA"
k = 1
characterReplacement(s,k)<jupyter_output><empty_output><jupyter_text>**Permutation in String****O(n)**Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.In other words, return true if one of s1's permutations is the substring of s2.**Solved with two pointers.** Example 1:Input: s1 = "ab", s2 = "eidbaooo"Output: trueExplanation: s2 contains one permutation of s1 ("ba").Example 2:Input: s1 = "ab", s2 = "eidboaoo"Output: false We need to have two pointers, one at the beginning of the string of s2 and the other starting from the len(s1). For each such window we could count the number of letters and if the count matches then we have a valid permutation. However, this would increase the time complexity to **O(26*n)**. Instead if we assign a variable equalling to the total number of matches, i.e. 26 as there are 26 alphabets, then we can optimise the time complexity to **O(n)**.Each time we move the right and left pointer, we compute the additional match of the character and if matches == 26 we return true.<jupyter_code>def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    # initialising the array of letter counts
    s1_count, s2_count = [0]* 26, [0] * 26
    # initialising the first n letter counts of 
    # s1 and s2 as per the len(s1)
    for i in range(len(s1)):
        s1_count[ord(s1[i]) - ord('a')] +=1
        s2_count[ord(s2[i]) - ord('a')] +=1
    matches = 0
    # initialising the matches variable once and from here on
    # only a single operation for the left and right side respectively
    # would be performed
    for i in range(26):
        matches +=1 if s1_count[i] == s2_count[i] else 0
    l_idx = 0
    # the right pointer starts from the letter > len(s1) until
    # the last letter
    for r_idx in range(len(s1),len(s2)):
        if matches == 26: return True
        # moving the right pointer to the next letter
        index = ord(s2[r_idx]) - ord('a')
        s2_count[index] +=1
        if s1_count[index] == s2_count[index]:
            matches +=1
        # the below case is when there is a duplicate letter in s2 side by side
        # which is also one of the letters in s1
        # s1 = "ab", s2 = "aibbaooo", when the right index is on the second 'b'
        elif s1_count[index] +1 == s2_count[index]:
            matches -=1
        # moving the left pointer to the next letter
        index = ord(s2[l_idx]) - ord('a')
        s2_count[index] -=1
        if s1_count[index] == s2_count[index]:
            matches +=1
        # the below case is when there is a letter in s1 which is being skipped
        # by the left pointer after it's move
        # s1 = "ab", s2 = "aibbaooo", when the left index is moving from 'a' to 'i'
        elif s1_count[index] -1 == s2_count[index]:
            matches -=1
        l_idx +=1
    

    return matches == 26
s1 = "abc"
s2 = "aibbbcaooo"
checkInclusion(s1,s2)<jupyter_output><empty_output><jupyter_text>**Generate Parentheses**Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example 1:Input: n = 3Output: ["((()))","(()())","(())()","()(())","()()()"]Example 2:Input: n = 1Output: ["()"] To find the number of valid(n) parentheses:* Closing parentheses == Opening parentheses* Opening parentheses < n* Closing parentheses < Opening parentheses* Stop when Closing parentheses == Opening parentheses == n<jupyter_code>from typing import List

def generateParenthesis(n: int) -> List[str]:
        stack = [] # to store the temporary parentheses combination
        result = [] # to store all the combinations
        
        # using recursively to add an opening or closing parenthese
        def parenthesis(opens, closes):
            if opens == closes == n:
                result.append(''.join(stack))
                return # if the above condition is True then python executes the append
                # and returns None, which means the following statements aren't executed
            if opens < n: # case where an opening parenthese can be added 
                stack.append('(')
                parenthesis(opens+1, closes) # increase the opening parenthese counter
                stack.pop() # removes the opening parenthese from the stack after the 
                # maximum number of opening parentheses have been added
                
            if closes < opens: # case where an closing parenthese can be added
                stack.append(')')
                parenthesis(opens, closes+1) # increase the closing parenthese counter
                stack.pop() # removes the closing parenthese from the stack after the
                # maximum number of closing parentheses have been added
        # starting the parenthesis function
        parenthesis(0,0)
        return result
generateParenthesis(3)<jupyter_output><empty_output><jupyter_text>**Daily Temperatures****O(n)**Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead. Example 1:Input: temperatures = [73,74,75,71,69,72,76,73]Output: [1,1,4,2,1,1,0,0]Example 2:Input: temperatures = [30,40,50,60]Output: [1,1,1,0]Example 3:Input: temperatures = [30,60,90]Output: [1,1,0]  temperatures = [73,74,75,71,69,72,76,73]While iterating through the entire array, keep adding the temps in a separate stack with their respective indexes until you find a temp which is larger than the first element of the stack. For instance, for `75` the next item is `71`, which is ` 69` so we pop it and subtract the index of `69` from `72` and it to the result array. As the stack is in descending order, `72` is still `>` than the first item in the stack i.e. `71`. We pop that and do the same. Next `72` < `75` so we add `72` to the stack and move to the next item `76`, which is bigger than both the items in the stack and therefore we pop them and add the result. Now we have two remaining numbers which aren't bigger than each other so we add `0` to the result array.<jupyter_code>from typing import List

def dailyTemperatures(temperatures: List[int]) -> List[int]:
        stack = [] # will contain [idx, temp] as we need both the index and temperature
        results = [0] * len(temperatures) # intialising the results array to the len of temperatures list
        # this will serve us later too as if we have an index for which there is no greater number in the following 
        # indexes then their respective indexes will be filled as 0
        for idx,temp in enumerate(temperatures):
            while stack and temp > stack[-1][1]: # this checks whether there is an element in the stack to compare to 
                # and if the current temp is > than the first temp in the stack then we pop it 
                stack_idx, stack_temp = stack.pop()
                results[stack_idx] = idx-stack_idx # the index of the first temp in the stack is the index in which
                # we need to store the result in the results array
            stack.append([idx,temp]) # if the stack is empty or if the next temp is smaller than the current temp
        return results
temperatures = [73,74,75,71,69,72,76,73]
dailyTemperatures(temperatures=temperatures)<jupyter_output><empty_output><jupyter_text>**Create Linked List Class**<jupyter_code>class Node: # individual element in the linked list
    def __init__(self, data=None, next=None): # two class members i.e. data and next(pointer to the next element)
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None #intially the linked list doesn't have any values so its head
        # isn't pointing to anything
    
    def insert_at_beginning(self, data):
        node = Node(data, self.head) # first create a Node with the data and point to the next 
        # item, which is the current head
        self.head = node # once the new node is created update the head to this one

    def insert_at_end(self, data):
        if self.head is None: # if the head is None then the current element becomes the
            # first/last element and points to None
            self.head = Node(data, None)
            return

        iterator = self.head # start with the head
        while iterator.next: # keep iterating through all the nodes, wherein the pointer points to a data point
            #  and not None, if the pointer points to None that means it's the last node in the linked list
            iterator = iterator.next
        iterator.next = Node(data, None) # upon reaching the last value, point the data as the 
        # next element of the current last node
    
    def insert_values(self, ls):
        self.head = None # reinitialise the linked list to contain 0 elements
        for i in ls:
            self.insert_at_end(i) # insert each element in the list as the last 
            # element in the linked list
            # instead of this, if you insert it at the beginning of the list then
            # you will have a reversed list

    def get_len(self):
        count =0
        iterator = self.head
        while iterator:
            iterator = iterator.next
            count +=1
        return count

    def remove_at_idx(self, idx):
        if idx<0 or idx>= self.get_len(): # as the counting starts with 0,
            # index cannot be equal to the length of the linked list
            raise Exception('Invalid Index.')
        
        if idx==0:
            self.head = self.head.next # if the index to drop is 0
            # then point the head to the next element
            return

        iterator = self.head # initialising an iterator
        count =0
        while count < idx-1: #stopping before the index to drop
            iterator = iterator.next # updating the iterator to the next element
            # in every call
            count +=1
        iterator.next = iterator.next.next # point the current element pointer 
        # by skipping one element(this is the element that we want to drop)

    def insert_at_idx(self, idx, data):
        if idx <0 or idx > self.get_len(): # if the index is > than the total length
            # however, if it's == length then insert it as well, which means 
            # insert at the last element
            raise Exception ('Invalid Index.')

        if idx==0:
            self.insert_at_beginning(data) 
            return
        
        count = 0
        iterator = self.head
        while count < idx-1:
            iterator = iterator.next
            count +=1
        node = Node(data, iterator.next) # create a new Node and assign the 
        # the pointer of this data to the next item of the iterator 
        # as the iterator has stopped before the index, it's currently
        # pointing to the next element, which we are accessing
        iterator.next = node


    def print_linked_list(self):
        if self.head is None:
            print('Linked List is empty.')
            return

        ll_str = '' # the string to append the linked list
        iterator = self.head # create an iterator at the head of the linked list
        while iterator: # while the iterator is not None
            ll_str += str(iterator.data) + ' --> ' # add the data to the string
            iterator = iterator.next # move to the next element
        print(ll_str)
ll = LinkedList()
ll.insert_at_beginning(1)
ll.insert_at_beginning(3)
ll.insert_at_beginning(4)
ll.insert_at_end(100)
ll.insert_at_end(200)
# print('Length of the linked list:', ll.get_len())
# ll.insert_values([201, 2020, 2300, 2400])
ll.remove_at_idx(2)
ll.insert_at_idx(3, 'jacob')
ll.print_linked_list()<jupyter_output>4 --> 3 --> 100 --> jacob --> 200 --><jupyter_text>**Reverse Linked List****O(n)**Given the head of a singly linked list, reverse the list, and return the reversed list. Example 1:Input: head = [1,2,3,4,5]Output: [5,4,3,2,1]Example 2:Input: head = [1,2]Output: [2,1]Example 3:Input: head = []Output: []<jupyter_code>def reverse_linked_list(head):
    previous, current = None, head
    while current:
        temp = current.next # storing the current element pointer in another variable
        current.next = previous # pointing the current element pointer to the previous
#             element which is None as it's the last one
        previous = current # moving the previous pointer to the current element
        current = temp # as we have stored the initial pointer of the current element, we are 
#             moving the current pointer to the next element that its pointing to
    return previous # as each of the pointers are now pointing in the reverse direction<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10515956330044089, 'fraction_numerical': 0.025299181188326685, 'mean_word_length': 2.791542288557214, 'pattern_counts': {'":': 0, '<': 132, '<?xml version=': 0, '>': 155, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '26', 'dir': 'jupyter-structured-clean-dedup', 'id': '659019', 'license': 'MIT', 'n_tokens_mistral': 12232, 'n_tokens_neox': 11508, 'n_words': 4487, 'path': 'dynamic_programming_notebook.ipynb', 'repo_name': 'shamik-biswas-rft/CodeSnippets', 'size': '38104'}