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).

 

cases:

when stand on the ith position of S:

1. if the character is not in T, do nothing;

2. if the character is in T:

　　start->i contains all characters in T: 

　　　　S[start] not in T or ((frequency of S[start] in start->i) > (frequency of S[start] in T))  start++

　　　　maxlen=max(i-start+1,maxlen), start++

 

use hashmap or int[256/128] to record the number of characters in t, int[] record is better.

 

class Solution {    public String minWindow(String s, String t) {        int[] cnum=new int[256];        int count=t.length();        for(char c:t.toCharArray()){            cnum[c]++;        }        int start=0;        int l=0;        int minlen=Integer.MAX_VALUE;        for(int r=0;r
     
      0){                count--;            }            cnum[s.charAt(r)]--;            if(count==0){                while(cnum[s.charAt(l)]<0){                    cnum[s.charAt(l)]++;                    l++;                }                if(r-l+1
     

 

注意不要老是笔误s.charAt()写成s.charAt[]！

cnum的index是字母的asc码，不要误写出cnum[l/r]之类，而是cnum[s.charAt(l/r)]！

return的时候不要掉以轻心，不要忘了如果没有满足条件的解的情况！