Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

Input and output examples

Example 1: Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC” Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2: Input: s = “a”, t = “a” Output: “a” Explanation: The entire string s is the minimum window.

Example 3: Input: s = “a”, t = “aa” Output: “” Explanation: Both ‘a’s from t must be included in the window. Since the largest window of s only has one ‘a’, return empty string.

Constraints:

m == s.length n == t.length 1 <= m, n <= 105 s and t consist of uppercase and lowercase English letters.

Solution

class Solution(object): def minWindow(self, s, t): """ :type s: str :type t: str :rtype: str """ if not s or not t or len(s) < len(t): return "" n = len(s) m = len(t) hash_map = {} for i in t: hash_map[i] = hash_map.get(i, 0) + 1 left = right = 0 count = len(hash_map) min_len = n+1 min_start = 0 while right < n: if s[right] in hash_map: hash_map[s[right]] -= 1 if hash_map[s[right]] == 0: count -= 1 right += 1 while count == 0: if right - left < min_len: min_len = right - left min_start = left if s[left] in hash_map: hash_map[s[left]] += 1 if hash_map[s[left]] > 0: count += 1 left += 1 if min_len == n+1: return "" return s[min_start:min_start+min_len]

Test the the solution:

import unittest

class TestSolution(unittest.TestCase): def setUp(self): self.s = Solution()

Reprint policy:
All articles in this blog are used except for special statements
CC BY 4.0
reprint policy. If reproduced, please indicate source
robot learner
!