substring search

🏠

The problem consists of finding a set of letters, e.g xyz into a string of letters yxzxzyzxyy.

brute force

Get all [[string substrings]], then check if [[string contains all chars unordered]].

 1def get_shortest_unique_substring(ar, s):
 2  min_length = float('inf')
 3  result = ''
 4  for i in range(len(s)):
 5    for j in range(i, len(s)):
 6      sub = s[i:j+1]
 7      contains = all(map(sub.count, ar))
 8      if contains and len(sub) < min_length:
 9        min_length = len(sub)
10        result = sub
11  return result
12
13res = get_shortest_unique_substring('xyyzyzyx', 'zyx')
14print(res)