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 "";
  8. const int ASCII_MAX = 256;
  9. int appeared_count[ASCII_MAX];
  10. int expected_count[ASCII_MAX];
  11. fill(appeared_count, appeared_count + ASCII_MAX, 0);
  12. fill(expected_count, expected_count + ASCII_MAX, 0);
  13. for (size_t i = 0; i < T.size(); i++) expected_count[T[i]]++;
  14. int minWidth = INT_MAX, min_start = 0; // 窗口大小,起点
  15. int wnd_start = 0;
  16. int appeared = 0; // 完整包含了一个T
  17. //尾指针不断往后扫
  18. for (size_t wnd_end = 0; wnd_end < S.size(); wnd_end++) {
  19. if (expected_count[S[wnd_end]] > 0) { // this char is a part of T
  20. appeared_count[S[wnd_end]]++;
  21. if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]])
  22. appeared++;
  23. }
  24. if (appeared == T.size()) { // 完整包含了一个T
  25. // 收缩头指针
  26. while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]]
  27. || expected_count[S[wnd_start]] == 0) {
  28. appeared_count[S[wnd_start]]--;
  29. wnd_start++;
  30. }
  31. if (minWidth > (wnd_end - wnd_start + 1)) {
  32. minWidth = wnd_end - wnd_start + 1;
  33. min_start = wnd_start;
  34. }
  35. }
  36. }
  37. if (minWidth == INT_MAX) return "";
  38. else return S.substr(min_start, minWidth);
  39. }
  40. };

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