Minimum Window Substring using bruteforce method

 

Description

Given two strings source and target. Return the minimum substring of source which contains each char of target.

1. If there is no answer, return "".
2. You are guaranteed that the answer is unique.
3. target may contain duplicate char, while the answer need to contain at least the same number of that char.
4. $0 <= len(source) <= 100000$

$0 <= len(target) <= 100000$

Example

Example 1:

Input:

source = "abc"
target = "ac"

Output:

"abc"

Explanation:

"abc" is the minimum substring of source string which contains each char of target "ac".

Example 2:

Input:

source = "adobecodebanc"
target = "abc"

Output:

"banc"

Explanation:

"banc" is the minimum substring of source string which contains each char of target "abc".

Example 3:

Input:

source = "abc"
target = "aa"

Output:

""

Explanation:

No substring contains two 'a'.

Challenge

O(n) time

 

Solution:

 

class Solution:

"""

@param source : A string

@param target: A string

@return: A string denote the minimum window, return "" if there is no such a string

"""

def checkExistsorNot(self, x,y):

reslt = all(list(map(lambda x: x in y,sorted(x))))

if (reslt):

dct = {}

for char in x:

dct[char] = x.count(char)

for key in dct:

val = dct[key]

temp = y.count(key)

if temp < val:

return False

return True

else:

return False

def minWindow(self, source , target):

minString = ""

j = 0

target = ''.join(sorted(target))

source = ''.join(sorted(source))

for i in range(0,len(source)+1):

for j in range(i,len(source)+1):

#print(source[i:j], target, target in source[i:j])

if self.checkExistsorNot(target, source[i:j]):

#print("Target Found", target)

if (minString != "" and len(source[i:j])<len(minString)):

minString = source[i:j]

break

if minString == "":

minString = source[i:j]

break

return minString

# write your code here