leetcode.76 Minimum window string

This Pro, at the first time I think of two pointer construct slidding windows, using map
but I find that it is so hard to continue with keep track of the status of T string in the map.

the idea is constructed a window, using two pointer, begin & end, end go forward, when the windows first contain the target word, begin pointer start go right, and once the map[c] ==0, it means that this char is from T. so we make map[c]++, and invalid the counter for next window.
the core code:

1
2
3
4
5
6
7
8
9
10
11
12
13
string minWindow(string s, string t){
	vector<int> map(128, 0);
	for(auto c: t) map[c]++;
	int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;
	while(end < s.size()){
		if(map[s[end++]]-- > 0) counter--; //this is hard to read, it means that every time it will //decrease
		while(counter==0){
			if(end-begin < d) d = end - (head = begin);
			if(map[s[begin++]]++==0) counter++; //invalid the counter
		}
	}
	return d==INT_MAX?"":s.substr(head, d);
}

// here is the template for most substr problem using sliding window solution:

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
int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){ 
                 
                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again
                
                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }

//One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.

1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++>0) counter++; 
            while(counter>0) if(map[s[begin++]]-->1) counter--;
            d=max(d, end-begin); //while valid, update d
        }
        return d;
    }