forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumWindowSubstring.java
More file actions
56 lines (53 loc) · 1.92 KB
/
MinimumWindowSubstring.java
File metadata and controls
56 lines (53 loc) · 1.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
Author: Andy, nkuwjg@gmail.com
Date: Dec 25, 2014
Problem: Minimum Window Substring
Difficulty: Medium
Source: https://oj.leetcode.com/problems/minimum-window-substring/
Notes:
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.
Solution: 1. Use two pointers: start and end.
First, move 'end'. After finding all the needed characters, move 'start'.
2. Use array as hashtable.
*/
public class Solution {
public String minWindow(String S, String T) {
int N = S.length(), M = T.length();
if (N < M) return new String("");
int[] need = new int[256];
int[] find = new int[256];
for (int i = 0; i < M; ++i)
need[T.charAt(i)]++;
int count = 0, resStart = -1, resEnd = N;
for (int start = 0, end = 0; end < N; ++end)
{
if (need[S.charAt(end)] == 0)
continue;
if (find[S.charAt(end)] < need[S.charAt(end)])
count++;
find[S.charAt(end)]++;
if (count != M) continue;
// move 'start'
for (; start < end; ++start) {
if (need[S.charAt(start)] == 0) continue;
if (find[S.charAt(start)] <= need[S.charAt(start)]) break;
find[S.charAt(start)]--;
}
// update result
if (end - start < resEnd - resStart) {
resStart = start;
resEnd = end;
}
}
return (resStart == -1) ? new String("") : S.substring(resStart, resEnd + 1);
}
}