# Java O(n) solution

• Use two pointer: i, j point to the start and end of the window. Move j forward until find a match window that includes all characters in string t. then move i forward to narrow down the window until if(i++), the window will not include all characters. assign this to the final pointer: resultI and resultJ if they are not initialized or larger than current i, j. then i++, and move j to repeat the steps until j reach the end of string s. Use hashMap to indicate how many(value) of the character (key) needed to cover t in s.substring(i, j). negative means still need more of the character, non-negative means had enough, extra number of the character.

``````public class Solution {
public String minWindow(String s, String t) {
if(s==null || s.length() == 0 || t == null || t.length() == 0) return "";

int sLen = s.length(), tLen = t.length(), count = 0;
int resultI =-1, resultJ = -1, i =0, j =0;
char c;
//create hashMap for target, indicate how many of each characters are needed
Map<Character, Integer> map = new HashMap<Character, Integer>();

for(int k=0; k<tLen; k++) {
c = t.charAt(k);
if(!map.containsKey(c)) map.put(c, -1);
else map.put(c, map.get(c)-1);
}

while(j<=sLen) {
if(count <tLen && j<sLen) {//j++
c = s.charAt(j);
if(map.containsKey(c)) {
int val = map.get(c)+1;
map.put(c,val);
if(val <= 0) count++;
}
j++;
} else if(count == tLen) {//i++
c = s.charAt(i);
if(map.containsKey(c)) {
map.put(c, map.get(c)-1);
if(map.get(c) < 0) {//i, j is the potential result
count--;
if((resultI == -1 && resultJ == -1) || (resultJ-resultI) >(j-i)) {
resultI = i;
resultJ = j;
}
}
}
i++;
} else break;//count <tLen && j==sLen
}
return (resultI>=0 && resultJ>=0)? s.substring(resultI, resultJ) : "";
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.