{"id":8940,"date":"2021-11-29T08:43:58","date_gmt":"2021-11-29T16:43:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8940"},"modified":"2021-11-29T08:46:12","modified_gmt":"2021-11-29T16:46:12","slug":"leetcode-76-minimum-window-substring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-76-minimum-window-substring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 76. Minimum Window Substring"},"content":{"rendered":"\n

Given two strings s<\/code> and t<\/code> of lengths m<\/code> and n<\/code> respectively, return the minimum window substring<\/strong> of <\/em>s<\/code> such that every character in <\/em>t<\/code> (including duplicates<\/strong>) is included in the window. If there is no such substring<\/em>, return the empty string <\/em>\"\"<\/code>.<\/em><\/p>\n\n\n\n

The testcases will be generated such that the answer is unique<\/strong>.<\/p>\n\n\n\n

A substring<\/strong> is a contiguous sequence of characters within the string.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> s = \"ADOBECODEBANC\", t = \"ABC\"\nOutput:<\/strong> \"BANC\"\nExplanation:<\/strong> The minimum window substring \"BANC\" includes 'A', 'B', and 'C' from string t.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"a\", t = \"a\"\nOutput:<\/strong> \"a\"\nExplanation:<\/strong> The entire string s is the minimum window.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"a\", t = \"aa\"\nOutput:<\/strong> \"\"\nExplanation:<\/strong> Both 'a's from t must be included in the window.\nSince the largest window of s only has one 'a', return empty string.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • m == s.length<\/code><\/li>
  • n == t.length<\/code><\/li>
  • 1 <= m, n <= 105<\/sup><\/code><\/li>
  • s<\/code> and t<\/code> consist of uppercase and lowercase English letters.<\/li><\/ul>\n\n\n\n
    Follow up:<\/strong> Could you find an algorithm that runs in O(m + n)<\/code> time?<\/p>\n\n\n\n
    Solution: Hashtable + Two Pointers<\/strong><\/h2>\n\n\n\n
    Use a hashtable to store the freq of characters we need to match for t.<\/p>\n\n\n\n
    Use (i, j) to track a subarray that contains all the chars in t.<\/p>\n\n\n\n
    Time complexity: O(m + n)
    Space complexity: O(m)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string minWindow(string s, string t) {\n    const int n = s.length();\n    const int m = t.length();\n    vector freq(128);\n    for (char c : t) ++freq[c];\n    int start = 0;\n    int l = INT_MAX;    \n    for (int i = 0, j = 0, left = m; j < n; ++j) {\n      if (--freq[s[j]] >= 0) --left;\n      while (left == 0) {\n        if (j - i + 1 < l) {\n          l = j - i + 1;\n          start = i;\n        }\n        if (++freq[s[i++]] == 1) ++left;\n      }\n    }\n    return l == INT_MAX ? \"\" : s.substr(start, l);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[176],"tags":[217,82,41,175],"class_list":["post-8940","post","type-post","status-publish","format-standard","hentry","category-two-pointers","tag-hard","tag-hashtable","tag-subarray","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8940","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8940"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8940\/revisions"}],"predecessor-version":[{"id":8942,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8940\/revisions\/8942"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}