C++ solution without DP O(n) time complexity and O(n) space


#1

int Solution::anytwo(string A) {
string s = A;
int n=s.length();

pair<int, int> ind[26][2];
memset(ind, -1, sizeof(ind));
map<int, int> mp;

int flag=0;

for(int i=0; i<n; i++){
	if(mp[s[i]] && ind[s[i]-'a'][0].second==-1){
		mp[s[i]]++;
		ind[s[i]-'a'][0].second=i;
	}
	else{
		mp[s[i]]++;
		ind[s[i]-'a'][0].first=i;
	}

	if(mp[s[i]]>2){
		flag=1;
		break;
	}
}
mp.clear();
for(int i=n-1; i>=0 && !flag; i--){
	if(mp[s[i]] && ind[s[i]-'a'][1].first==-1) ind[s[i]-'a'][1].first=i;
	else ind[s[i]-'a'][1].second=i;
	mp[s[i]]++;
}

for(int i=0; i<26; i++){
	for(int j=i+1; j<26; j++){
		if(ind[i][0].second!=-1 && ind[j][1].second!=-1 && ind[i][0].first<ind[j][1].first && ind[i][0].second<ind[j][1].second){
			flag=1;
			break;
		}
	}
}
return flag;

}