Given an array of unique characters
arr
and a stringstr
, implement a functiongetShortestUniqueSubstring
that finds the smallest substring ofstr
containing all the characters inarr
. 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)