Average of all contiguous sub-arrays of size K (intro)

def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    windowSum += arr[windowEnd]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if windowEnd >= K - 1:
      result.append(windowSum / K)  # calculate the average
      windowSum -= arr[windowStart]  # subtract the element going out
      windowStart += 1  # slide the window ahead

  return result

Maximum Sum Subarray of size K

def max_sub_array_of_size_k(k, arr):

  if arr is None:
    return None

  globalMax = float('-inf')

  windowStart = 0
  windowSum = 0

  # Iterate right pointer
  for end in range(len(arr)):

    windowSum += arr[end]

    # If window is now the size of k...
    if end >= k - 1:
      globalMax = max(windowSum, globalMax)
      windowSum -= arr[windowStart]
      windowStart += 1
  
  return globalMax

Smallest Subarray with a given sum

import math

def smallest_subarray_with_given_sum(s, arr):
  windowStart= 0
  minSubarray = math.inf
  windowSum = 0

  for windowEnd in range(len(arr)):
    windowSum += arr[windowEnd]

    while windowSum >= s:
      minSubarray = min(minSubarray, (windowEnd - windowStart + 1))
      windowSum -= arr[windowStart]
      windowStart += 1

    if minSubarray is 1:
      return 1

  if minSubarray is math.inf:
    return 0

  return minSubarray

Longest Substring with maximum k distinct characters

Again, this one uses the basic sliding window template. This time, we use a dictionary to keep track the number of occurrences of each character in our dictionary. The length of the dictionary is the number of unique characters. When value hits 0, we remove it with del d[key].

def longest_substring_with_k_distinct(str1, k):
  
  if len(str1) is 0 or k <= 0:
    return 0

  d = {}
  runningMax = 0
  windowStart, windowEnd = 0, 0

  for windowEnd in range(len(str1)):

    rightChar = str1[windowEnd]

    if rightChar not in d:
      d[rightChar] = 0

    d[rightChar] += 1

    # If we have more than k distinct chars, then shrink window until we
    # have k distint chars
    while len(d) > k:
      leftChar = str1[windowStart]
      d[leftChar] -= 1
      if d[leftChar] is 0:
        del d[leftChar]
      windowStart += 1
      
    runningMax = max(runningMax, windowEnd - windowStart + 1)

  return runningMax

Fruits into Baskets

This one is pretty much the exact same as "Longest Substring with k distinct characters" above. In this case, k is the number of baskets which is equal to 2.

def fruits_into_baskets(fruits):
  if len(fruits) is 0:
    return 0

  windowStart = 0
  d = {}
  runningMax = 0

  for windowEnd in range(len(fruits)):

    rightFruit = fruits[windowEnd]

    if rightFruit not in d:
      d[rightFruit] = 0

    d[rightFruit] += 1

    while len(d) > 2:
      leftFruit = fruits[windowStart]
      d[leftFruit] -= 1
      if d[leftFruit] is 0:
        del d[leftFruit]
      windowStart += 1
    
    runningMax = max(runningMax, windowEnd - windowStart + 1)
      

  return runningMax

Longest Substring with Distinct Characters

Similar to the above 2 problems. Instead of keeping track of the number of occurences, we keep track of the most recent index of each character. Even if past characters are before our window, they will be in the dictionary. So, if they are in our dictionary, we only move windowStart if the index in within our window ( > windowStart).

def non_repeat_substring(str):
  if len(str) is 0:
    return 0
  
  windowStart = 0
  d = {}
  runningMax = 0

  for windowEnd in range(len(str)):
    rightChar = str[windowEnd]

    if rightChar in d:
      windowStart = max(windowStart, d[rightChar] + 1)

    d[rightChar] = windowEnd

    runningMax = max(runningMax, windowEnd - windowStart + 1)


  return runningMax

Longest Substring with Same Letter After Replacement

Similar to longest substring with k distinct characters. The most occurring character in the window has max(d.values()) occurrences in the window. It might be more efficient to keep a running max of the most occurring character, rather than checking the max of the dictionary every loop.

def length_of_longest_substring(str, k):
  
  if len(str) is 0:
    return 0

  windowStart = 0
  d = {}
  runningMax = 0

  for windowEnd in range(len(str)):

    rightChar = str[windowEnd]

    if rightChar not in d:
      d[rightChar] = 0

    d[rightChar] += 1

    while (windowEnd - windowStart + 1) > (max(d.values()) + k):
      
      leftChar = str[windowStart]
      d[leftChar] -= 1
      if d[leftChar] is 0:
        del d[leftChar]
      windowStart += 1

    runningMax = max(runningMax, windowEnd - windowStart + 1)

  return runningMax

Longest Subarray with Ones After Replacement

Similar to above..

def length_of_longest_substring(arr, k):
  windowStart = 0
  runningMax = 0
  d = {}
  d[0] = 0
  d[1] = 0

  for windowEnd in range(len(arr)):

    rightNum = arr[windowEnd]

    if rightNum not in d:
      d[rightNum] = 0

    d[rightNum] += 1

    # Shrink window
    # While window size is greater than numbers of 1s + k...
    while (windowEnd - windowStart + 1) > (d[1] + k):
      leftNum = arr[windowStart]
      d[leftNum] -= 1
      windowStart += 1
    
    runningMax = max(runningMax, windowEnd - windowStart + 1)


  return runningMax

Permutations in a String

Got it on first submission. Used Counter to get occurrences of each letter in pattern. Then, subtract window occurrences from this counts dictionary. If all the counts are equal to 0 and window size is equal to length of pattern, then return True.

from collections import Counter

def find_permutation(str, pattern):

  if len(pattern) > len(str):
    return False

  counts = Counter(pattern)
  windowStart = 0

  for windowEnd in range(len(str)):
    rightChar = str[windowEnd]
    if rightChar in counts:
      counts[rightChar] -= 1
    
    # Window size is equal to length of pattern
    if (windowEnd - windowStart + 1) is len(pattern):
      if all(count is 0 for count in counts.values()):
        return True
      leftChar = str[windowStart]
      if leftChar in counts:
        counts[leftChar] += 1
      windowStart += 1
 

  return False

String Anagrams

Pretty much the exact same as above, except keep track of starting indexes.

from collections import Counter

def find_string_anagrams(str, pattern):

  result_indexes = []
  windowStart = 0
  counts = Counter(pattern)

  for windowEnd in range(len(str)):

    rightChar = str[windowEnd]

    if rightChar in counts:
      counts[rightChar] -= 1


    # Window is equal to length of str
    if (windowEnd - windowStart + 1) is len(pattern):
      if all(count is 0 for count in counts.values()):
        result_indexes.append(windowStart)

      leftChar = str[windowStart]

      if leftChar in counts:
        counts[leftChar] += 1

      windowStart += 1

  return result_indexes

Smallest Window Containing Substring

Like above, need to keep track of pattern counts. Once we have all the characters in the substring, keep shrinking the window until we no longer have all the characters.

from collections import Counter

def find_substring(str, pattern):

  counts = Counter(pattern)
  windowStart = 0
  outputString = ""

  for windowEnd in range(len(str)):
    rightChar = str[windowEnd]
    if rightChar in counts:
      counts[rightChar] -= 1
    
    # We have all characters in window. Shrink window
    while all(count <= 0 for count in counts.values()):

      if len(outputString) is 0 or (windowEnd - windowStart + 1) < len(outputString):
        outputString = str[windowStart : windowEnd + 1]
      
      leftChar = str[windowStart];
      if leftChar in counts:
        counts[leftChar] += 1
      windowStart += 1
  
  return outputString

Word Concatenation

Not the most efficient solution, but was accepted on leetcode.

from collections import Counter

def find_word_concatenation(str, words):

  result_indices = []
  counts = Counter(words)
  wordLen = len(words[0])
  totalLen = wordLen * len(words)

  for i in range(len(str)):
    d = dict(counts)
    for j in range(i, i + totalLen, wordLen):
      s = str[j:j+wordLen]
      if s in d:
        d[s] -= 1
    if all(count is 0 for count in d.values()):
      result_indices.append(i)

    
  return result_indices