How to Solve ‘minSubstringWithAllChars’ in CodeFights

The Problem:

You have two strings, s and t. The string t contains only unique elements. Find and return the minimum consecutive substring of s that contains all of the elements from t.

It’s guaranteed that the answer exists. If there are several answers, return the one which starts from the smallest index.

Example

For s = "adobecodebanc" and t = "abc", the output should be
minSubstringWithAllChars(s, t) = "banc".

Input/Output

  • [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

The Solution:

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 ""

The Explanation:

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s