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)