You have two strings,
t. The string
t contains only unique elements. Find and return the minimum consecutive substring of
s that contains all of the elements from
It’s guaranteed that the answer exists. If there are several answers, return the one which starts from the smallest index.
s = "adobecodebanc" and
t = "abc", the output should be
minSubstringWithAllChars(s, t) = "banc".
- [time limit] 4000ms (py)
- [input] string sA string consisting only of lowercase English letters.Guaranteed constraints:
0 ≤ s.length ≤ 100.
- [input] string tA string consisting only of unique lowercase English letters.Guaranteed constraints:
0 ≤ t.length ≤ min(26, s.length).
- [output] string
def minSubstringWithAllChars(s, t): for x in range(len(s)+1): for p in range(len(s)-x+1): c = filter(lambda x: x in t,s[p:p+x]) if len(set(c))==len(t): return s[p:p+x] return ""
First of all, if this was a problem with bigger inputs, this solution would not be efficient at all.
What this code does is to select all substrings with length 0,1,2,… up to len(s), and try to see if any of them have all the characters. The code is written in a manner to minimize the effort. So, checking if we have all the elements is done using filter and set.
How this works is:
We filter out all letters in our substrings that are not in t. For example, b,a,n,c becomes b,a,c, then we count the number of unique elements in this filtered substring. If it is equal to the length of t, then, we have at least one of each element in t in our substring, too.
Another example, if our substring was cababddefg and t = “abcg”, then, filtered substring wouold be “cababg” and set will give “cabg”. Following this, the length of t and the length of our filtered subset is the same.