‘substring’ problems solving template

Jimmy (xiaoke) Shen
1 min readDec 23, 2019

--

I got the template from the link below:

It is related to problem

76. Minimum Window Substring

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

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;
}

--

--

No responses yet