Case study: Find smallest substring containing all distinct character in pattern string

 Here is the link. 

	/*
	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).
	Example:
	Input: S = "ADOBECODEBANC", T = "ABC"
	Output: "BANC"
	string minWindow(string s, string t) {
	}
	*/
	//
	// test your own code
	//
	string minWindow(string s, string t) {
	int lenT = t.length();
	int lenS = s.length();
	if(lenT == 0 || lenS == 0) return "";
	if(lenS < lenT) return "";
	string res;
	unordered_map<char,int> tMap; // assuming that all are distinct
	for(auto ch:t){
	tMap[ch] = 0; // 1 ++; tMap[ch]++;
	} // keep count - sliding window -
	int cnt =0;
	int j = 0; // left variable
	int unq_cnt =0;
	// pretend to be an itnerviewee from Facebook, google
	//
	for(int i=0; i < lenS; ++i){
	if(tMap.find(s[i]) == tMap.end()) continue; // skip
	if(tMap[s[i]] == 0) unq_cnt++; // add count
	tMap[s[i]]++; // how
	while(unq_cnt == lenT){ // find all chars - not enough
	int tempLen = i-j+1;
	/*
	if(tempLen == lenT){
	return s.substr(j, tempLen); // return? - ????? break for loop on line 101 - will not visit all chars in original string
	}*/
	if(res == "" || tempLen < res.size()){ // res - final minimum one
	res = s.substr(j, tempLen);
	}
	if(tMap.find(s[j]) != tMap.end()){ // left char - in pattern string
	if(tMap[s[j]]-1 == 0){ // only one - decrement
	unq_cnt-=1;
	}
	tMap[s[j]]--; // decrement one
	}
	j = j+1; // left pointer - slide window left pointer - continiuoly
	}
	}
	return res;
	}

view raw FindShortestSubStringContainingPatternDistinctChars.cpp hosted with ❤ by GitHub