LeetCode Q159: Longest Substring with At Most Two Distinct Characters (hard)

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

Solution:

To solve substring problem, could use following template:

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

view raw Q76-3.cpp hosted with ❤ by GitHub

My solution is:

	class Solution {
	public:
	int lengthOfLongestSubstringTwoDistinct(string s) {
	vector<int> map(128, 0);
	int counter=0;
	int start=0, end=0;
	int d=0;
	while(end<s.size()){
	if(map[s[end]]!=0){
	map[s[end]]+=1;
	end++;
	continue;
	}
	if(map[s[end]]==0){
	if(counter<2){
	map[s[end]]+=1;
	counter++;
	end++;
	continue;
	}
	if(counter==2){
	d=end-start>d? end-start:d;
	while(counter==2){
	map[s[start]]-=1;
	if(map[s[start]]==0)
	counter--;
	start++;
	}
	}
	}
	}
	return max(d, end-start);
	}
	};

view raw Q159.cpp hosted with ❤ by GitHub

A better solution is:

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

view raw Q76-4.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int lengthOfLongestSubstringTwoDistinct(string s) {
	int res=0;
	if(s.length()==0)
	return res;
	int p0=0, p1=0;
	vector<int> myHash(128, 0);
	int count=0;
	while(p1<s.length()){
	char c = s[p1];
	if(myHash[c]==0)
	count++;
	myHash[c]++;
	if(count>2){
	while(p0<s.length()){
	if(--myHash[s[p0++]]==0)
	break;
	}
	count--;
	}else
	res = max(res, p1-p0+1);
	p1++;
	}
	return res;
	}
	};

view raw Q159Rnd2.cpp hosted with ❤ by GitHub

Rnd3 sol:

	int lengthOfLongestSubstringTwoDistinct(string s) {
	int res=0;
	if(s.empty())
	return res;
	unordered_map<char, int> myMap;
	int p0=0, p1=0;
	int count = 0;
	while(p1<s.length()){
	char c = s[p1];
	myMap[c]++;
	count = myMap[c]==1? count+1:count;
	if(count>2){
	while(p0<s.length()-1&&--myMap[s[p0++]]!=0){}
	count--;
	}
	res = max(res, p1-p0+1);
	p1++;
	}
	return res;
	}

view raw Q159Rnd3.cpp hosted with ❤ by GitHub