Minimum Window Substring

描述

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example, S = "ADOBECODEBANC", T = "ABC"

Minimum window is "BANC".

Note:

  • If there is no such window in S that covers all characters in T, return the emtpy string "".
  • If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

    分析

双指针，动态维护一个区间。尾指针不断往后扫，当扫到有一个窗口包含了所有T的字符后，然后再收缩头指针，直到不能再收缩为止。最后记录所有可能的情况中窗口最小的

代码

  1. // LeetCode, Minimum Window Substring
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     string minWindow(string S, string T) {
  6.         if (S.empty()) return "";
  7.         if (S.size() < T.size()) return "";
  9.         const int ASCII_MAX = 256;
  10.         int appeared_count[ASCII_MAX];
  11.         int expected_count[ASCII_MAX];
  12.         fill(appeared_count, appeared_count + ASCII_MAX, 0);
  13.         fill(expected_count, expected_count + ASCII_MAX, 0);
  15.         for (size_t i = 0; i < T.size(); i++) expected_count[T[i]]++;
  17.         int minWidth = INT_MAX, min_start = 0;  // 窗口大小，起点
  18.         int wnd_start = 0;
  19.         int appeared = 0;  // 完整包含了一个T
  20.         //尾指针不断往后扫
  21.         for (size_t wnd_end = 0; wnd_end < S.size(); wnd_end++) {
  22.             if (expected_count[S[wnd_end]] > 0)  {  // this char is a part of T
  23.                 appeared_count[S[wnd_end]]++;
  24.                 if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]])
  25.                     appeared++;
  26.             }
  27.             if (appeared == T.size()) {  // 完整包含了一个T
  28.                 // 收缩头指针
  29.                 while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]]
  30.                         || expected_count[S[wnd_start]] == 0) {
  31.                     appeared_count[S[wnd_start]]--;
  32.                     wnd_start++;
  33.                 }
  34.                 if (minWidth > (wnd_end - wnd_start + 1)) {
  35.                     minWidth = wnd_end - wnd_start + 1;
  36.                     min_start = wnd_start;
  37.                 }
  38.             }
  39.         }
  41.         if (minWidth == INT_MAX) return "";
  42.         else return S.substr(min_start, minWidth);
  43.     }
  44. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/minimum-window-substring.html