Given strings str1 and str2, find the minimum (contiguous) substring W of str1, so that str2 is a subsequence of W.
If there is no such window in str1 that covers all characters in str2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.
 
Example 1:
Input: 
str1: geeksforgeeks
str2: eksrg
Output: 
eksforg
Explanation: 
Eksforg satisfies all required conditions. str2 is its subsequence and it is longest and leftmost among all possible valid substrings of str1.
Example 2:
Input: 
str1: abcdebdde
str2: bde
Output: 
bcde
Explanation: 
"bcde" is the answer and "deb" is not a smaller window because the elements of T in the window must occur in order.
Your Task:
Complete the function string minWindow(string str1, string str2), which takes two strings as input and returns the required valid string as output.
Expected Time Complexity: O(N^{2}).
Expected Auxiliary Space: O(N^{2}).
Constraints:
0 <= str1 <= 1000
0 <= str2 <= 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: #User function Template for python3

 

class Solution:

    def minWindow(self, str1, str2):

        # Code here

Solutions:
class Solution:

	def minWindow(self, s, t):
		if not s or not t:
			return ''
		(n, m) = (len(s), len(t))
		ans = ''
		for i in range(n):
			if s[i] != t[0]:
				continue
			(j, k) = (i + 1, 1)
			while j < n and k < m:
				if s[j] == t[k]:
					j += 1
					k += 1
				else:
					j += 1
			if k == m:
				if not ans or j - i < len(ans):
					ans = s[i:j]
		return ans


class Solution:

	def minWindow(self, str1, str2):
		n = len(str1)
		m = len(str2)
		a = []
		ans = ''
		l = 999
		for i in range(n):
			if str1[i] == str2[0]:
				a.append(i)
		for z in a:
			s = str1[z + 1:]
			c = 1
			p = 0
			while c < m and p < len(s):
				if s[p] == str2[c]:
					if c == m - 1:
						if l > p + 2:
							l = p + 2
							ans = str1[z:z + p + 2]
					p += 1
					c += 1
				else:
					p += 1
		return ans


import math
import bisect

class Solution:

	def minWindow(self, str1, str2):
		s = 0
		ans_s = None
		min_win = math.inf
		while s < len(str1):
			(k, e) = (0, s)
			if str1[s] != str2[k]:
				s += 1
				continue
			else:
				while k < len(str2) and e < len(str1):
					if str1[e] == str2[k]:
						e += 1
						k += 1
						continue
					else:
						e += 1
					if e - s + 1 >= min_win:
						break
				if k >= len(str2):
					if e - s < min_win:
						ans_s = s
						min_win = e - s
			s += 1
		return str1[ans_s:ans_s + min_win] if min_win != math.inf else ''


import math
import bisect

class Solution:

	def minWindow(self, str1, str2):
		ans_ind = None
		min_win = math.inf
		if not str1 or not str2:
			return ''
		arr = [[] for i in range(27)]
		for i in range(len(str1)):
			arr[ord(str1[i]) - ord('a')].append(i)

		def getInd(char, preInd):
			a = arr[ord(char) - ord('a')]
			ind = bisect.bisect_right(a, preInd)
			return ind if ind < len(a) else -1
		xk = arr[ord(str2[0]) - ord('a')]
		for index in xk:
			k = 0
			isbreak = False
			ja = index
			for j in range(index, len(str1)):
				if k >= len(str2):
					break
				ja += 1
				if j - index + 1 >= min_win:
					break
				if str1[j] == str2[k]:
					k += 1
					continue
				else:
					ind = getInd(str2[k], j)
					if ind == -1:
						isbreak = True
						break
			if isbreak:
				break
			if k >= len(str2):
				if ja - index < min_win:
					ans_ind = index
					min_win = ja - index
		if min_win == math.inf:
			return ''
		return str1[ans_ind:ans_ind + min_win]


class Solution:

	def minWindow(self, str1, str2):
		j = 0
		min_str = 10000
		ans_str = ''
		for i in range(len(str1)):
			x = ''
			if str1[i] != str2[0]:
				continue
			for p in range(i, len(str1)):
				x += str1[p]
				if str1[p] == str2[j]:
					j += 1
				if j == len(str2):
					if min_str == p - i:
						break
					min_str = min(min_str, p - i)
					if min_str == p - i:
						ans_str = x
					break
			j = 0
		if min_str == 10000:
			return ''
		return ans_str


import math

class Solution:

	def minWindow(self, str1, str2):
		l1 = list((x for x in str2))
		tracker = 0
		l = 0
		res_l = math.inf
		res = ''
		r = 0
		while r < len(str1):
			if str1[r] == l1[tracker]:
				tracker += 1
			while tracker == len(l1):
				if res_l > r - l + 1:
					res_l = r - l + 1
					res = str1[l:r + 1]
				if str1[l] == l1[0]:
					tracker = 0
					r = l
				l += 1
			r += 1
		return res


class Solution:

	def minWindow(self, str1, str2):
		right = 0
		i = 0
		ans = (float('inf'), None, None)
		while right < len(str1):
			if str1[right] == str2[i]:
				i += 1
			if i == len(str2):
				i -= 1
				left = right
				while i >= 0:
					if str1[left] == str2[i]:
						i -= 1
					left -= 1
				if right - left + 1 < ans[0]:
					ans = (right - left + 1, left + 1, right + 1)
				i = 0
			right += 1
		return str1[ans[1]:ans[2]] if ans[1] is not None and ans[2] is not None else ''


class Solution:

	def minWindow(self, str1, str2):
		(i, j) = (0, 0)
		i2 = 0
		n1 = len(str1)
		n2 = len(str2)
		res = ''
		maxi = [n1, '']
		while j < n1:
			if str1[j] == str2[i2]:
				res += str1[j]
				i2 += 1
				if i2 == n2:
					if j - i + 1 < maxi[0]:
						maxi[0] = j - i + 1
						maxi[1] = res
					i += 1
					j = i
					i2 = 0
					res = ''
				else:
					j += 1
			else:
				if res != '':
					res += str1[j]
				elif res == '':
					i += 1
				j += 1
		return maxi[1]


import math
import collections

class Solution:

	def minWindow(self, str1, str2):
		min_len = math.inf
		min_win = ''
		if len(str1) < len(str2):
			(str1, str2) = (str2, str1)
		(l, idx) = (0, 0)
		for r in range(len(str1)):
			if str1[r] == str2[idx]:
				idx += 1
			if idx >= len(str2):
				l = r
				idx -= 1
				while idx >= 0:
					if str1[l] == str2[idx]:
						idx -= 1
					l -= 1
				if r - l + 1 < min_len:
					min_win = str1[l + 1:r + 1]
					min_len = r - l + 1
				idx = 0
				l = r + 1
		return min_win


class Solution:

	def minWindow(self, str1, str2):
		i = 0
		d = {}
		while i < len(str1):
			k = i
			j = 0
			while j < len(str2) and k < len(str1):
				if str1[k] == str2[j]:
					if j == len(str2) - 1:
						if len(d) == 0:
							d[0] = str1[i:k + 1]
							break
						elif len(d[0]) > len(str1[i:k + 1]):
							d[0] = str1[i:k + 1]
					j += 1
				if k == i and j == 0:
					break
				k += 1
			i += 1
		if len(d) > 0:
			return d[0]
		else:
			return ''


class Solution:

	def minWindow(self, str1, str2):
		res = ''
		n = len(str1)
		l = -1
		while l < n:
			l = Solution.find_first(str1, n, str2[0], l + 1)
			r = l + 1
			index = 1
			while index < len(str2) and r < n:
				if str1[r] == str2[index]:
					index += 1
				r += 1
			if index < len(str2):
				return res
			elif res == '' or len(str1[l:r]) < len(res):
				res = str1[l:r]
				if len(str2) == 1:
					return res
		return res

	def find_first(stri, n, c, i):
		while i < n and stri[i] != c:
			i += 1
		return i


class Solution:

	def minWindow(self, str1, str2):
		(size_str1, size_str2) = (len(str1), len(str2))
		length = float('inf')
		minimum_subsequence = ''
		(index_s1, index_s2) = (0, 0)
		while index_s1 < size_str1:
			if str1[index_s1] == str2[index_s2]:
				index_s2 += 1
				if index_s2 == size_str2:
					(start, end) = (index_s1, index_s1 + 1)
					index_s2 -= 1
					while index_s2 >= 0:
						if str1[start] == str2[index_s2]:
							index_s2 -= 1
						start -= 1
					start += 1
					if end - start < length:
						length = end - start
						minimum_subsequence = str1[start:end]
					index_s1 = start
					index_s2 = 0
			index_s1 += 1
		return minimum_subsequence