76 Minimum Window Substring
1. Question
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 empty string""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
2. Implementation
(1) Two Pointer + Hash
class Solution {
public String minWindow(String s, String t) {
int[] map = new int[256];
int count = t.length();
int minLen = Integer.MAX_VALUE;
int minStart = 0, minEnd = 0, start = 0 , end = 0;
for (char c : t.toCharArray()) {
++map[c];
}
while (end < s.length()) {
if (map[s.charAt(end)] >= 1) {
--count;
}
--map[s.charAt(end)];
++end;
while (count == 0) {
if (end - start < minLen) {
minEnd = end;
minStart = start;
minLen = end - start;
}
if (map[s.charAt(start)] >= 0) {
++count;
}
++map[s.charAt(start)];
++start;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minEnd);
}
}
3. Time & Space Complexity
(1) Two Pointer + Hash: 时间复杂度O(n), 空间复杂度O(1)
Last updated
Was this helpful?