0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ It would be much easier to evaluate if you included comments... \$\endgroup\$ – Snowbody Dec 9 '17 at 7:34
  • \$\begingroup\$ @Snowbody that's part of the code review. \$\endgroup\$ – Daniel Dec 9 '17 at 7:59
  • \$\begingroup\$ @Snowbody: added. \$\endgroup\$ – noman pouigt Dec 9 '17 at 8:01
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Can you provide a example with some words? \$\endgroup\$ – noman pouigt Dec 10 '17 at 5:37
  • \$\begingroup\$ @nomanpouigt Do you mean something like looking for smallest substring of hello in a Wikipedia article? I've also updated the explanation so it may make more sense now. \$\endgroup\$ – Neil Dec 10 '17 at 5:40
  • \$\begingroup\$ I mean substr:xyz in string:txyuxyyzxyz ? \$\endgroup\$ – noman pouigt Dec 10 '17 at 5:42
  • \$\begingroup\$ Returns yzx and is done with 35% faster(as input gets larger the efficiency difference will increase). If you are wondering, yours returns the same thing. \$\endgroup\$ – Neil Dec 10 '17 at 5:46
  • \$\begingroup\$ I think you misunderstood my comment. I just want to understand your algorithm and it would be better if you can explain it with an example. \$\endgroup\$ – noman pouigt Dec 10 '17 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.