Minimum window substring using python containing substr in any order

Question

Given an array of unique characters arr and a string str, implement a function getShortestUniqueSubstring that finds the smallest substring of str containing all the characters in arr. Return "" (empty string) if such a substring doesn’t exist.

This algorithm is used.

import collections
import sys

def get_shortest_unique_substring(substring, string):
  def trim_left(substring, window, count):
    ''' find how much left pointer can be moved in a window where all substring is present'''
    for left, c in enumerate(window):
      if c in count and count[c] > 1:
        count[c] -= 1
      elif c not in count:
        continue
      else:
        return left
    return 0

  substring = set(substring)
  ''' validating input '''
  if not substring or not string:
    return ""
  if len(substring) == len(string) and substring == set(string):
    return string

  window, min_window, min_window_len = [], [], sys.maxint
  left, right, count = 0, 0, collections.Counter()
  # to check if the initial minimum window has been found which has all the substring
  substr_found = set(substring)

  for right, c in enumerate(string):
    if c in substring:
      count[c] += 1
      if c in substr_found:
        substr_found.remove(c)
      # window has been found and now trim left pointer as much as possible maintaining the invariant that substr is still present between left and right pointers
      if not substr_found:
        left += trim_left(substring, string[left:right+1], count)
        # update the minimum window
        if right - left + 1 < min_window_len:
          min_window_len, min_window = right - left + 1, string[left:right+1]
        # we can't find better window than the length of substr
        if len(min_window) == len(substring):
          return "".join(min_window)
  return "".join(min_window)

Answer 1

Overview

Interesting algorithm. I looked over it and tried to find a bit simpler of a way. Basically, I implemented the modified version with a dictionary. The dictionary stores the data in the formation char:index. Every time we run into a relevant character we update the dictionary. This eliminates all need for back tracking via trim_left. Every time we updated our dictionary of character locations, we would get a string by finding the min and max of the dictionary. If that string is smaller, then we assign it to the smallest variable.

Performance

Typically the newer version performs a lot faster. This can be explained by referring to big O notation. Yours, because of back tracking, performs at O(n^2) or worse. However, the newer version doesn't back track so much, and it sticks to only modifying one dictionary so the new version worst case scenario is O(n) efficiency. (Or, to be more specific, it is O(nm) where n is the length of your string and m is the length of the substring; however there is a very logical limit to the length of substring m, so it will probably never be worse than O(64n) [note: we convert the string to a set to remove duplicates]).

New Code

def newShortest(subString, string):
  myChars = set(subString)
  smallest = ""
  current={}
  for i, char in enumerate(string):
    if char in myChars:
      current[char] = i
      if len(current) == len(myChars):
        temp = string[current[min(current,key=current.get)]:current[max(current,key=current.get)]+1]
        if len(temp) < len(smallest) or len(smallest) == 0:
          smallest = temp
  return smallest

Code used to time your version vs modified version

I switched out the args for smaller and larger sizes:

import time

args = ["hello","I would like to all over you hehhhhhkkkkkkkkkklo"]

def timeIt(func,args):
  then = time.time()
  for _ in range(10000):
    func(*args)
  print("{} timing: {:.2f}".format(func.__name__, time.time()-then))

timeIt(newShortest,args)
timeIt(get_shortest_unique_substring,args)