Generalization: substring search problem Template:
class Solution {
public:
T minWindow(string s, string t) {
if(t.length() > s.length()) return "";
unordered_map <char, int> map;
for(int i = 0; i < t.length(); i++ ){
++map[t[i]];
}
int left = 0, right = 0, head = INT_MAX, len = INT_MAX, count = map.size();
while(right < s.length()){
char rightChar = s[right];
if(map.find(rightChar) != map.end()){
if(--map[rightChar] == 0) count --; // here condition statement and -- or ++ depending on cases
}
right ++;
while(count == 0){ // here condition statement depends on cases
// do
// increment
char leftChar = s[left];
if (map.find(leftChar)!= map.end()){
if(++map[leftChar] > 0){
count++;
}
}
left ++;
}
}
return T; //<answer to return>;
}
};
Original Java Code from the LeetCode Forum harrychaoyanghe
public class Solution {
public List<Integer> slidingWindowTemplateByHarryChaoyangHe(String s, String t) {
//init a collection or int value to save the result according the question.
List<Integer> result = new LinkedList<>();
if(t.length()> s.length()) return result;
//create a hashmap to save the Characters of the target substring.
//(K, V) = (Character, Frequence of the Characters)
Map<Character, Integer> map = new HashMap<>();
for(char c : t.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
//maintain a counter to check whether match the target string.
int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate.
//Two Pointers: begin - left pointer of the window; end - right pointer of the window
int begin = 0, end = 0;
//the length of the substring which match the target string.
int len = Integer.MAX_VALUE;
//loop at the begining of the source string
while(end < s.length()){
char c = s.charAt(end);//get a character
if( map.containsKey(c) ){
map.put(c, map.get(c)-1);// plus or minus one
if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition).
}
end++;
//increase begin pointer to make it invalid/valid again
while(counter == 0 /* counter condition. different question may have different condition */){
char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer
if(map.containsKey(tempc)){
map.put(tempc, map.get(tempc) + 1);//plus or minus one
if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition).
}
/* save / update(min/max) the result if find a target*/
// result collections or result int value
begin++;
}
}
return result;
}
}
Longest Substring with At Most Two Distinct Characters, Longest Substring with At Most K Distinct Characters, Minimum Window Substring, Longest Substring Without Repeating Characters
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;
}
Minimum Window Substring
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--; //in t
while(counter==0){ //valid
if(end-begin<d) d=end-(head=begin);
if(map[s[begin++]]++==0) counter++; //make it invalid
}
}
return d==INT_MAX? "":s.substr(head, d);
}
Longest Substring with At Most Two Distinct Characters:
int lengthOfLongestSubstringTwoDistinct(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>2) if(map[s[begin++]]--==1) counter--;
d=max(d, end-begin);
}
return d;
}
Longest Substring Without Repeating Characters
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;
}
Special thanks: LeetCode Discussion Forum for the reference!