CareerCup

c1 = first unique character
c2 = second unique character

sp1 = first position of c1
ep1 = last position of c1
sp2 = first position of c2
ep2 = last position of c2

Initialize c1=s[0]; sp1=ep1=0
c2=-1

For each s[i]:
	if s[i] != c1 AND c2 is not initialized i.e. c2 == -1 :
		 //initialize c2,sp2,ep2
	else if s[i] == c2:
		//update end position of c2
	else if s[i] == c1:
		//we define second unique character as the last character found 
		//in the substring of 2 unique characters so far
		//so we have to swap c1 and c2 and their start and end positions
		//s[i] i.e. c1 becomes c2 and c2 becomes c1
		//Do required variable swappings
	else if s[i] != c1 and s[i] != c2 i.e. s[i] is a new character:
		//c2 will become c1 while s[i] will become c2
		//Now here is the corner case due to which we need both start and
		//end positions of c1 and c2
		//Our new substring containing 2 unique characters must start from 
		//the point after which there is no occurence of c1 till i i.e 
		//after the last position of c1
		//So make required updates in sp1, sp2, ep1, ep2

In this algo, keep track of the start and end positions of current substringof 2 unique characters +
keep track of max length such substring found so far.

Complexity : O(n)

//Code

char * func( char *s, int len ) {
	char c1, c2;
	int sp1, sp2, i;
	int ep1, ep2;
	
	sp2 = ep2 = c2 = -1;
	c1 = s[0];
	sp1 = ep1 = 0;
	
	int ans_sp, ans_ep; //starting and ending point of overall answer
	int cur_ans_sp, cur_ans_ep;//starting and ending point of current required substring at any instant
	
	ans_sp = ans_ep = 0;
	cur_ans_sp = cur_ans_ep = 0;

	for( i = 1; i < len; i++ ) {
		if( s[i] != c1 && c2 == -1 ) {
			c2 = s[i];
			sp2 = ep2 = i;
			cur_ans_ep++;
		} else if( s[i] == c1 ) {
			c1 = c2;
			sp1 = sp2;
			ep1 = ep2;
			c2 = s[i];
			sp2 = ep1+1; 
			ep2 = i;
			cur_ans_ep++;
		} else if( s[i] == c2 ) {
			ep2 = i;
			cur_ans_ep++;
		} else if( s[i] != c1 && s[i] != c2 ) {
			c1 = c2;
			sp1 = ep1+1;
			ep1 = ep2;
			c2 = s[i];
			sp2 = ep2 = i;
			cur_ans_sp = sp1;
			cur_ans_ep = ep2;
		}
		
		if( cur_ans_ep-cur_ans_sp+1 > ans_ep-ans_sp+1 ) {
			ans_sp = cur_ans_sp;
			ans_ep = cur_ans_ep;
		}
	}

	for( i = 0; i < ans_ep-ans_sp+1; i++ ) {
		s[i] = s[ans_sp+i];
	}
	
	s[i] = '\0';
	
	return s;

}

Solution with nice explanation of a similar problem
coders-stop[.]blogspot[.]in/2012/09/directi-online-test-number-of[.]html

public class LongestSubStringWith2Char {
	
	public String findString(String str){
		int firstFreq, nextFreq, totalCount, end = 0;
		Character firstChar, secondChar;
		
		//Initially make the characters and frequencies to numm
		firstChar = secondChar = null;
		firstFreq = nextFreq = totalCount=0;
		
		for(int i=0; i<str.length(); i++){
			char ch = str.charAt(i);
			
			//Increase the frequecy based on the character found
			if(firstChar == null){
				firstChar = ch;
				firstFreq++;
			}
			else if(ch == firstChar)
				firstFreq++;
			else if(secondChar == null){
				secondChar = ch;
				nextFreq++;
			}
			else if(ch == secondChar)
				nextFreq++;
			
			// If character is not in the last two list, start new sequence
			if(ch != firstChar && ch != secondChar){
				firstChar = secondChar;
				firstFreq = nextFreq;
				secondChar = ch;
				nextFreq = 1;
			}
			
			//If the sequece is bigger than previous found, make this a bigger
			if(totalCount < nextFreq + firstFreq){
				end = i+1;
				totalCount = firstFreq + nextFreq;
			}
		}
		
		return str.substring(end - totalCount, end);
	}
	
	public static void main(String[] args) {
		LongestSubStringWith2Char demo = new LongestSubStringWith2Char();
		System.out.println(demo.findString("aabbcbbbadef"));
		System.out.println(demo.findString("aabbaacdef"));
		System.out.println(demo.findString("abbbbbbaddeeffff"));
		System.out.println(demo.findString("ffeeeeeeeeeeedddddddddddbbbbbbbbbaaaaaa"));
	}
}

Maintain two chars, When a new char is encountered, move back the pointer as far as possible such that there are only two strings in the string. And then expand the string to the front as well.

public class LongestSubstring {

	public static void main(String[] args) {
		char[] str = "abbbbbbaddeeffff".toCharArray();
		char char1 = ' ';
		char char2 = ' ';
		
		//Maintain a buffer and a live string where operations are done. 
		StringBuffer longestString = new StringBuffer();
		StringBuffer longestStringBuffer = new StringBuffer();
		
		//iterate through the arr. 
		for(int index=0; index<str.length; index++)
		{
			char newChar = str[index];
			if(char1 == ' ' || newChar == char1)
			{
				char1 = newChar;
				longestString.append(char1);
				continue;
			}
			if(char2 == ' ' || newChar == char2)
			{
				char2 = newChar;
				longestString.append(char2);
				continue;
			}
			
			//Encountered a new char, say 'c'
			if(longestString.length() > longestStringBuffer.length())
				longestStringBuffer = longestString;
			longestString = new StringBuffer();
			
			//Note the prev Character and go back as far as possible so that the characters are only of type prev char, say 'b' 
			char prevChar = str[index-1];
			int j = 0;
			for( j = index-2; j>=0; j-- )
			{
				if(prevChar == str[j])
					continue; 
				break;
			}
			//Append to the longest string from the farthest possible point.  
			for(int k=++j; k<index; k++)
			{
				longestString.append(str[k]);
			}
			char1 = prevChar; 
			char2 = str[index];
			//Append the current char too. 
			longestString.append(str[index]);
		}
		//Just in case we found a long string in the end. 
		if(longestString.length() > longestStringBuffer.length())
			longestStringBuffer = longestString;
		System.out.println(longestStringBuffer);
	}

}

def longest_substr_two_uniqe_char(onestr):
max_len=beg=end=0
first_pos=-1
second_pos=-1
index=0
while index<len(onestr):
if first_pos==-1:
first_pos=index
elif second_pos==-1:
second_pos=index
elif onestr[index]!=onestr[first_pos] and onestr[index] !=onestr[second_pos]:
break
else:
index+=1
# index-=1
while index<len(onestr):
if index-first_pos+1>max_len:
max_len=index-first_pos+1
beg=first_pos
end=index

first_pos=second_pos
second_pos=index
while index<len(onestr) and (onestr[index]==onestr[second_pos] or onestr[index]==onestr[first_pos]):
index+=1
if index==len(onestr):
if index-first_pos>max_len:
beg=first_pos
end=index
print beg,end
return onestr[beg:end]

bug free is so difficult:
def longest_substr_two_uniqe_char(onestr):
max_len=beg=end=0
first_pos=-1
second_pos=-1
index=0
while index<len(onestr):
if first_pos==-1:
first_pos=index
elif second_pos==-1:
second_pos=index
elif onestr[index]!=onestr[first_pos] and onestr[index] !=onestr[second_pos]:
break
else:
index+=1
# index-=1
while index<len(onestr):
if index-first_pos+1>max_len:
max_len=index-first_pos+1
beg=first_pos
end=index

first_pos=second_pos
index=first_pos
while index<len(onestr) and onestr[index]==onestr[first_pos]: #case aabaadddddaa
index+=1
second_pos=index
while index<len(onestr) and (onestr[index]==onestr[second_pos] or onestr[index]==onestr[first_pos]):
index+=1
if index==len(onestr):
if index-first_pos>max_len:
beg=first_pos
end=index
print beg,end
return onestr[beg:end]

void substring(const char* const input)
{
    char letters[2] = {0,0};
    char currentLetter = 0;
    int currentLength = 0;
    int overallLength = 0;
    int bestOverallLength = 0;
    int bestStartIndex;
    
    const int inputLength = (int)strlen(input);
    for(int i = 0; i < inputLength; ++i)
    {
        char thisLetter = input[i];
        
        // update "letters"
        if(letters[0] == 0)
        {
            letters[0] = thisLetter;
            currentLetter = thisLetter;
            currentLength = 1;
            overallLength = 1;
        }
        else if(letters[1] == 0)
        {
            if(thisLetter == currentLetter)
            {
                ++currentLength;
            }
            else
            {
                letters[1] = thisLetter;
                currentLetter = thisLetter;
                currentLength = 1;
            }
            ++overallLength;
        }
        else if((thisLetter == letters[0]) || (thisLetter == letters[1]))
        {
            if(thisLetter == currentLetter)
            {
                ++currentLength;
            }
            else
            {
                currentLetter = thisLetter;
                currentLength = 1;
            }
            ++overallLength;
        }
        else
        {
            letters[0] = currentLetter;
            letters[1] = thisLetter;
            currentLetter = thisLetter;
            overallLength = currentLength + 1;
            currentLength = 1;
        }
        
        
        if(overallLength > bestOverallLength)
        {
            bestOverallLength = overallLength;
            bestStartIndex = (i - bestOverallLength) + 1;
        }
    }
    
    printf("%d at %d\n",bestOverallLength,bestStartIndex);
}

public class Questions {

    public static void main(String[] args) {
        
        //String input = "aabbcbbbadef";
        String input = "aabcbcbcbcbcbcbcbcbcbbccbaa";
        String result = longestSubstringContaining2Characters(input);
        System.out.println("Longest subString for '" + input + "' is '" + result + "'");
    }
    
    /*
     * Given a string, find the longest substring in it such that the substring contains only 2 unique characters.
     * Ex. aabbcbbbadef ---->>>>  bbcbbb
     */
    public static String longestSubstringContaining2Characters(String input) {
        String longestSubstring = "";
        
        Character firstCharacter, secondCharacter;
        firstCharacter = secondCharacter = null;
        int firstCharacterIndex, secondCharacterIndex;
        firstCharacterIndex = secondCharacterIndex = -1;
        
        for (int i = 0; i < input.length(); i++) {
            char currentCharacter = input.charAt(i);
            
            if (secondCharacter == null && firstCharacter != null) {
                secondCharacter = currentCharacter;
                secondCharacterIndex = i;
            } else if (firstCharacter == null) {
                firstCharacter = currentCharacter;
                firstCharacterIndex = i;
            }
            
            if (firstCharacter == secondCharacter) {
                secondCharacter = currentCharacter;
                secondCharacterIndex = i;
            }
            
            if ((secondCharacter != null) && (currentCharacter != firstCharacter && currentCharacter != secondCharacter)) {
                String currentSubString = input.substring(firstCharacterIndex, i);
                if (currentSubString.length() > longestSubstring.length()) {
                    longestSubstring = currentSubString;
                }
                firstCharacter = secondCharacter;
                firstCharacterIndex = secondCharacterIndex;
                
                secondCharacter = currentCharacter;
                secondCharacterIndex = i;
            }
            
        }
        
        return longestSubstring;
    }
}

My attempt:

Scanner in=new Scanner(System.in);
        String theLetters=in.nextLine();
        String[] theLetterArray=theLetters.split("");
        Map<Integer,String> letterSubStrings=new HashMap<> ();
        int subLength=0;
        int start=1;
        int end=1;
        String letter1=theLetterArray[1];
        String letter2="";String cachedLetter2="";
        int lastOccLetter2=1;
        String output="";
        
        for(int i=1;i<theLetterArray.length;i++){
            if(theLetterArray[i].equals(letter1)){
                subLength++;
                if(!letter1.equals(cachedLetter2)){
                    lastOccLetter2=i;
                    cachedLetter2=letter1;
                }
            }else if(theLetterArray[i].equals(letter2)){
                subLength++;
                if(!letter2.equals(cachedLetter2)){
                    lastOccLetter2=i;
                    cachedLetter2=letter2;
                }
            }else if(letter2.equals("")) {
                letter2=theLetterArray[i];
                cachedLetter2=theLetterArray[i];
                lastOccLetter2=i;
                subLength++;
            }else{
                end=i;
                String subString="";
                for(int j=start;j<end;j++){
                    subString+=theLetterArray[j];
                }
                letterSubStrings.put(subLength, subString);
                start=lastOccLetter2;
                subLength=1;
                letter1=letter2;
                letter2=theLetterArray[i];
            }
            
        }
        output=letterSubStrings.get(Collections.max(letterSubStrings.keySet()));
        System.out.println(output);

import java.util.*;
import java.io.*;

public class findSubstring {

public String findString(String str){
int firstFreq, nextFreq, totalCount, firstPlace, nextPlace, start;
String result= new String();
Character firstChar, secondChar;

//Initially make the characters and frequencies to numm
firstChar = secondChar = null;
firstFreq = nextFreq = totalCount=firstPlace=nextPlace=start=0;

for (int i=0;i<str.length();i++){
char ch=str.charAt(i);

if (firstChar==null && secondChar==null){
firstFreq ++;
firstChar = ch;
firstPlace=i;
start=i;
}
else if (secondChar==null && firstChar == ch){
firstFreq ++;
}
else if (secondChar==null){
nextFreq ++;
secondChar = ch;
nextPlace = i;
}
else if (firstChar == ch && firstPlace < nextPlace){
firstFreq ++;
firstPlace=i;
}
else if (firstChar == ch && firstPlace > nextPlace){
firstFreq ++;
}
else if (secondChar == ch && firstPlace < nextPlace){
nextFreq ++;
}
else if (secondChar == ch && firstPlace > nextPlace){
nextFreq ++;
nextPlace = i;
}
else{
if (totalCount<firstFreq+nextFreq){
totalCount=firstFreq+nextFreq;
result = str.substring(start, i);
}
if (firstPlace<nextPlace){
firstChar=secondChar;
secondChar=ch;
firstPlace=nextPlace;
start=nextPlace;
}
else {
secondChar=ch;
start=firstPlace;
}
nextPlace=i;
firstFreq=i-firstPlace;
nextFreq=1;
continue;
}
if (totalCount<firstFreq+nextFreq){
totalCount=firstFreq+nextFreq;
result = str.substring(start, i+1);
}
}


return result;
}

public static void main(String[] args) {
findSubstring demo = new findSubstring();
System.out.println(demo.findString("aabbcbbbadef"));
System.out.println(demo.findString("aabbaacdef"));
System.out.println(demo.findString("abbbbbbaddeeffff"));
System.out.println(demo.findString("ffeeeeeeeeeeedddddddddddbbbbbbbbbaaaaaa"));
System.out.println(demo.findString("aabaadddddaa"));
}
}

import java.util.*;
import java.io.*;

public class findSubstring {
	
	public String findString(String str){
		int firstFreq, nextFreq, totalCount, firstPlace, nextPlace, start;
		String result= new String();
		Character firstChar, secondChar;
		
		//Initially make the characters and frequencies to numm
		firstChar = secondChar = null;
		firstFreq = nextFreq = totalCount=firstPlace=nextPlace=start=0;
		
		for (int i=0;i<str.length();i++){
			char ch=str.charAt(i);
			
			if (firstChar==null && secondChar==null){
				firstFreq ++;
				firstChar = ch;
				firstPlace=i;
				start=i;
			}
			else if (secondChar==null && firstChar == ch){
				firstFreq ++;
			}
			else if (secondChar==null){
				nextFreq ++;
				secondChar = ch;
				nextPlace = i;
			}
			else if (firstChar == ch && firstPlace < nextPlace){
				firstFreq ++;
				firstPlace=i;
			}
			else if (firstChar == ch && firstPlace > nextPlace){
				firstFreq ++;
			}
			else if (secondChar == ch && firstPlace < nextPlace){
				nextFreq ++;
			}
			else if (secondChar == ch && firstPlace > nextPlace){
				nextFreq ++;
				nextPlace = i;
			}
			else{
				if (totalCount<firstFreq+nextFreq){
					totalCount=firstFreq+nextFreq;
					result = str.substring(start, i);
				}			
				if (firstPlace<nextPlace){
					firstChar=secondChar;
					secondChar=ch;
					firstPlace=nextPlace;
					start=nextPlace;
				}
				else {
					secondChar=ch;
					start=firstPlace;
				}
				nextPlace=i;
				firstFreq=i-firstPlace;
				nextFreq=1;
				continue;
			}
			if (totalCount<firstFreq+nextFreq){
				totalCount=firstFreq+nextFreq;
				result = str.substring(start, i+1);
			}
		}
		
		
		return result;
	}
	
	public static void main(String[] args) {
		findSubstring demo = new findSubstring();
		System.out.println(demo.findString("aabbcbbbadef"));
		System.out.println(demo.findString("aabbaacdef"));
		System.out.println(demo.findString("abbbbbbaddeeffff"));
		System.out.println(demo.findString("ffeeeeeeeeeeedddddddddddbbbbbbbbbaaaaaa"));
		System.out.println(demo.findString("aabaadddddaa"));
	}
}

In this algo, keep track of the start and end positions of current substring of 2 unique characters + keep track of max-length-substring found so far.

ALGORITHM {
c1 = first unique character (leftMost)
c2 = second unique character (rightMost)

sp1 = first position of c1
ep1 = last position of c1
sp2 = first position of c2
ep2 = last position of c2

global_sp = 0;
global_ep = 0;

Initialize c1=s[0]; sp1=ep1=0; c2=-1; sp2=ep2=-1;

For each s[i], from i = 0 to s.lastIndex(), do {
if ((s[i] != c1) && (c2 is not initialized i.e. c2 == -1)) {
// initialize (c2, sp2, ep2);
// c2 = s[i]; sp2=i; ep2=i;

} else if (s[i] == c2) {
// update end position of c2;

} else if (s[i] == c1) {
// update end position of c1;

} else if ((s[i] != c1) && (s[i] != c2), i.e., s[i] is a new character) {
// (1) Shift c1 to c2 by coping smartly.
if (s[i-1] == c1) {
// COPY: c1 into c1
c1 = c1;
sp1 = MAX(ep2+1, sp1);
ep1 = i-1;

} else { // (s[i-1] == c2)
// COPY: c2 into c1
c1 = c2;
sp1 = MAX(ep1+1, sp2);
ep1 = i-1;
}

// (2) UPDATE: (c2, sp2, ep2) values from (s[i], i, i)
}


// compare lengths of local and global max-subString found so far.
if(c2 == -1) {
local_max_length = (ep1 - sp1 + 1);
} else {
local_max_length = (MAX(ep1, ep2) - MIN(sp1, sp2) + 1);
}
if( local_max_length > (global_ep - global_sp + 1) ) {
global_sp = sp1;
global_ep = ep2;
}
}

return ( substring(s, global_sp, global_ep) );
}

Complexity : O(n)

//file name maxsubstr_uniq.cpp
//

#include <iostream>
#include <string>

namespace {
    using std::string;
    using std::cout;
    using std::cin;
    typedef string::const_iterator c_str_iterator;
};

string maxsubstr(const string& s) {
    c_str_iterator max_l, max_r, curr_l, curr_r, next_l, last;

    max_l = max_r = curr_l = next_l = s.begin(); 
    curr_r  = curr_l + 1 ;
    for(last = s.end() ; curr_r < last; ) {
        if( *curr_r != *(curr_r - 1) ) { //transition
            if(*curr_l != *curr_r && *curr_l != *(curr_r -1)) //2 transitions?
                curr_l = next_l; //update new sequence start
            next_l = curr_r; //update where next new sequence starts
        }
        ++curr_r; 
        if( max_r - max_l < curr_r - curr_l) { //update max
            max_r = curr_r;
            max_l = curr_l;
        }
    }
    return string(max_l,max_r);
}

int main() {
    string s;
    cout << "input string,output string\n";
    while ( cin >> s ) {
        cout << s << "," << maxsubstr(s) << "\n";
    }
    cout << "" << "," << maxsubstr("") << "\n";
}

//cat teststrings.txt
//a
//ab
//abc
//abb
//abbc
//abbcc
//ababc
//abcabbbbcdddddd
//aabbaacdef
//abbbbbbaddeeffff
//ffeeeeeeeeeeedddddddddddbbbbbbbbbaaaaaa
//aabaadddddaa

//g++ maxsubstr_uniq.cpp -o maxsubstr
//./maxsubstr < teststrings.txt
//input string,output string
//a,
//ab,ab
//abc,ab
//abb,abb
//abbc,abb
//abbcc,bbcc
//ababc,abab
//abcabbbbcdddddd,cdddddd
//aabbaacdef,aabbaac
//abbbbbbaddeeffff,abbbbbbadd
//ffeeeeeeeeeeedddddddddddbbbbbbbbbaaaaaa,eeeeeeeeeeeddddddddddd
//aabaadddddaa,aabaadddddaa
//,

Working C Code with edge cases considered
Time Complexity : O(n)
Each time I start with the intention of writing some clean and elegant code but inevitably end with a not so pleasing piece

/* Program to find the length longest substring which has 
two and only two unique characters */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int longest2CharSS(char *str, int len);
int findPos(char *str, int i);

int main(void)
{
	char str[]={"aabbabbbadef"};
	int len=strlen(str);
	
	//Calling longest2CharSS() within the 
	//print statement itself
	printf("\nThe length of the longest such substring : %d\n", 
	longest2CharSS(str, len));
	
	return 0;
	
}

//Function that returns the length of the longest such substring
int longest2CharSS( char *str, int len)
{
	if(len==0 || len==1)				//Edge case where two unique  
	{									//characters are out of the question
		printf("Error!\n");
		exit(0);
	}
	
	char twoch[2];				//Two characters array to store the two unique 
				 			    //characters of the current valid substring
	
	int start, end, len_lss, i=1, l_start, l_end, j=0;
	twoch[0]=str[0];
	char cpstr[len];
	
	while(str[i]==twoch[0])		//To get to the next distinct character 
		i++;
		
	if(i>=len)
	{
		printf("Error!\n");
		exit(0);
	}
	
	twoch[1]=str[i];
	
	start=0;l_start=0;
	end=i;l_end=0;
	
	while(i<len)
	{
		if(str[i]!=twoch[0] && str[i]!=twoch[1])// If a new character is seen
		{
			start=findPos(str, i-1);//Start is assigned the position of the least 
									//recent continuous str[i-1] character
									
			end=i;
			
			if((end-start)>len_lss)//If current valid substring has a length 
			{	len_lss=end-start; //greater than the length of the longest 
								   //valid substring seen until now
				
				l_start=start;
				l_end=end;
			}
		}
		
 		else if((str[i]==twoch[0])^(str[i]==twoch[1])) //If the present character 
		{											  //is same as any one of the 
			end++;									  //present valid substring character
			
			if((end-start)>len_lss)
			{	len_lss=end-start;
			
				l_start=start;
				l_end=end;
			
			}	
		}
		
		i++;
	}
	
	for(i=l_start; i<=l_end-1;i++)//Copy the longest substring into cpstr
	{	
		cpstr[j]=str[i];
		j++;
	}	
	printf("The longest such substring : %s", cpstr);
	
	return len_lss;//Returning length of the longest substring
}

//Function to find the position of the oldest occurrence of the 
//character condition being that it is a continuous occurrence
int findPos(char *str, int i)
{
	int j=i;
	
	while(str[j]==str[i])
		j--;
	
	return (j+1);
}

Here is simple solution:

char* FindMax(const char* s)
{
        vector<unsigned> v;
        unsigned len = strlen(s);
        if (len < 2) return strdup(s);
        char c = s[0];
        for (int i=1; i<len; i++) {
                if (s[i] == c) continue;
                v.push_back(i);
                c = s[i];
        }
        if (v.size() <= 2) return strdup(s);
        int max = 0;
        int i1 = 0;
        int i2 = 0;
        for (int i=1; i<v.size()-1; i++) {
                if (v[i-1] + v[i+1] > max) {
                        i1 = v[i-1];
                        i2 = v[i+1] - 1;
                }
        }
        return strdup(string(s, i1, i2).c_str());
}

int main(int argv, char** argc[])
{
        const char* s1 = "abbbbbbcccdddd";
        cout << FindMax(s1) << endl;
        return 0;
}

Solution in python

def find_substring(S, k=1):
    if len(S) < 2:
        return S

    charmap = {}        # Track counts for each char
    unique = 0          # Track the number of unique characters
    longest = ''        # Track the longest word
    start, end = 0, 0   # Iteration pointers
    while end < len(S):
        if unique <= k:
            end += 1
            newchar = S[end - 1]
            charmap[newchar] = charmap.get(newchar, 0) + 1
            if charmap[newchar] == 1:
                unique += 1
        else:
            start += 1
            remchar = S[start - 1]
            charmap[remchar] = charmap[remchar] - 1
            if charmap[remchar] == 0:
                unique -= 1
        if len(S[start:end]) > len(longest) and unique <= k:
            longest = S[start:end]
    return longest



input = 'aabbcbbbadef'

print find_substring(input, k=2)

//filename maxsubstr_uniq.cpp

#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::cin;
typedef string::const_iterator c_str_iterator;

void update_max(c_str_iterator& max_l,c_str_iterator& max_r,
		c_str_iterator curr_l,c_str_iterator curr_r) {
    if( max_r - max_l >= curr_r - curr_l) return;
    max_l = curr_l;
    max_r = curr_r;
}

string maxsubstr(const string& s) {
    if(!s.size()) return s;
    c_str_iterator max_l, max_r, curr_l, 
	           curr_r, sec, next_l,last;
    max_l = max_r = curr_l = sec = next_l = s.begin(); 
    curr_r  = curr_l + 1;
    for(last = s.end() ; curr_r < last; ) {
	for( ; sec < last && *sec == *curr_l; ++sec);
	for( ; curr_r < last && *curr_r == *sec || *curr_r == *curr_l; ++curr_r) {
	    if(*next_l != *curr_r)
		next_l = curr_r;
	}
	update_max(max_l,max_r,curr_l,curr_r);
	curr_l = next_l;
	sec = curr_r;
    }
    update_max(max_l,max_r,curr_l,last);
    return string(max_l,max_r);
}

int main() {
    string s;
    cout << "input string,output string\n";
    while ( cin >> s ) {
        cout << s << "," << maxsubstr(s) << "\n";
    }
    cout << "" << "," << maxsubstr("") << "\n";
}

// g++ maxsubstr_uniq.cpp -o maxsubstr
//./maxsubstr < teststrings.txt
//input string,output string
//a,a
//ab,ab
//abc,ab
//abb,abb
//abbc,abb
//abbcc,bbcc
//ababc,abab
//abcabbbbcdddddd,cdddddd
//aabbaacdef,aabbaa
//abbbbbbaddeeffff,abbbbbba
//ffeeeeeeeeeeedddddddddddbbbbbbbbbaaaaaa,eeeeeeeeeeeddddddddddd
//aabaadddddaa,aadddddaa
//,

public static String bigSeqs(String str) {
		char c[] = str.toCharArray();
		char c1, c2 = 0, lc;
		int s1, s2 = 0, start = 0, bigstart = 0, bigend = 0;
		if (c.length > 0) {
			s1 = 0;
			c1 = c[0];
			lc = c1;
		} else
			return null;
		for (int i = 1; i < c.length; i++) {
			if (c2 == 0 && c[i] != c1) {
				c2 = c[i];
				s2 = i;
			} else if (c[i] != c1 && c[i] != c2) {
				if (i - start > bigend - bigstart) {
					bigstart = start;
					bigend = i;
				}

				if (lc == c2) {
					c1 = c2;
					s1 = s2;
				}
				start = s1;
				c2 = c[i];
				s2 = i;
			} else if (lc == c1 && c[i] == c2) {
				s2 = i;
			} else if (lc == c2 && c[i] == c1) {
				s1 = i;
			} else if (i == c.length - 1) {
				if (i + 1 - start > bigend - bigstart) {
					bigstart = start;
					bigend = i + 1;
				}
			}
			lc = c[i];
		}
		if (bigend == 0)
			bigend = c.length;
		return str.substring(bigstart, bigend);
	}

This version builds longest substrings adding one char at the time in front of the current one and examines each char (at most) only twice: once when t is put on the current longest substring, and once if a third char is found in front of it; when the latter happens, the pointer to the beginning of the substring is advanced to the earliest point where either of the two characters it actually contains no longer appears in it

def smallest_2char_subsequence(s):
  if len(s) <= 2:
    return s
  
  char_count = {}
  
  fst_char = s[0]
  char_count[fst_char] = 1
  
  i = 1
  j = 0
  while i < len(s) and s[i] == fst_char:
    i += 1
    char_count[fst_char] += 1

  if i == len(s):
    return s
  
  snd_char = s[i]
  char_count[snd_char] = 1
  max_len = 0
  start = 0
  
  while i < len(s):
    if s[i] == fst_char:
      char_count[fst_char] += 1
      i += 1
    elif s[i] == snd_char:
      char_count[snd_char]
      i += 1
    else:
      # s[i] != fst_char, s[i] != snd_Char
      if i - j > max_len:
        max_len = i - j
        start = j
      
      while char_count[fst_char] > 0 and char_count[snd_char] > 0:
        char_count[s[j]] -= 1
        j += 1
        
      if char_count[fst_char] == 0:
        fst_char = s[i]
        char_count[fst_char] = 1
      else:
        snd_char = s[i]
        char_count[snd_char] = 1
      
      i += 1
  
  if i - j > max_len:
    max_len = i - j
    start = j
    
  return s[start:start + max_len]

This version builds longest substrings adding one char at the time in front of the current one and examines each char (at most) only once, when it is added in front of the current longest substring; when a third char is found, the pointer to the beginning of the substring is advanced to the earliest point where either of the two characters it actually contains no longer appears in it

def smallest_2char_subsequence(s):
  if len(s) <= 2:
    return s
  
  last_occurrence = {}
  
  fst_char = s[0]
  last_occurrence[fst_char] = 0
  
  i = 1
  j = 0
  while i < len(s) and s[i] == fst_char:
    i += 1
    last_occurrence[fst_char] = i

  if i == len(s):
    return s
  
  snd_char = s[i]
  last_occurrence[snd_char] = i
  max_len = 0
  start = 0
  
  while i < len(s):
    if s[i] == fst_char:
      last_occurrence[fst_char] = i
    elif s[i] == snd_char:
      last_occurrence[snd_char] = i
    else:
      # s[i] != fst_char, s[i] != snd_Char
      if i - j > max_len:
        max_len = i - j
        start = j
      
      if last_occurrence[fst_char] < last_occurrence[snd_char]:
        j = last_occurrence[fst_char] + 1
        del last_occurrence[fst_char]
        fst_char = s[i]
        last_occurrence[fst_char] = i
      else:
        j = last_occurrence[snd_char] + 1
        del last_occurrence[snd_char]
        snd_char = s[i]
        last_occurrence[snd_char] = i

    i += 1
  
  if i - j > max_len:
    max_len = i - j
    start = j
    
  return s[start:start + max_len]

Seems like it can be done simpler than most of the solutions above:

import java.util.HashSet;
import java.util.Set;

public class LongestSubstringWithNChars {
	
	public String getSubString(final String string, final int numChars){
		if(string == null || string.isEmpty())
			return "";
		
		int start = 0, end = 0;
		Set<Character> chars = new HashSet<Character>();
		chars.add(string.charAt(start));
		
		// start with first character
		String longest = "" + string.charAt(start);
		int longestSize = 1;
		
		while(end != string.length()-1){
			end++;
			if(!chars.contains(string.charAt(end))){
				if(chars.size() != numChars){
					chars.add(string.charAt(end));
				} else{
					// check if current is longest
					int len = end - start;
					if(len >= longestSize){
						longestSize = len;
						longest = string.substring(start, end);
					}
					
					// move up
					chars = new HashSet<Character>();
					start = end;
					while(start > 0 && (chars.size() != numChars || chars.contains(string.charAt(start)))){
						chars.add(string.charAt(start));
						start--;
					}
					start++;
				}
			}
		}
		int len = end - start;
		if(len > longestSize){
			longestSize = len;
			longest = string.substring(start, end+1);
		}
		
		return longest;
	}
	
}

static void findLongestSubstring(String target)
	{
		if(target==null || target.length()==0) return ;
		char first=target.charAt(0);
		char second='\0';
		int maxLength=0; 
		String maxString=""; 
		int start1=0;
		int start2=0; 
		for(int i=0; i<target.length(); i++)
		{
			if(second=='\0')
			{
				if(target.charAt(i)!=first)
				{
					second=target.charAt(i); 
					start2=i; 
				}		
			}else
			{
				if(target.charAt(i)!=first && target.charAt(i)!=second)
				{
					int minValue=Math.min(start1 , start2); 
					if(i-minValue>maxLength)
					{
						maxLength= i-minValue;
						maxString=target.substring(minValue, i);
					}				
					if(start1<start2)
					{
						start1=i; 
						first=target.charAt(i);
					}else
					{
						start2=i; 
						second=target.charAt(i);
					}
				}
			}
		}
		System.out.println(maxString);
		
	}

Time: O(n)
Space:O(1)

def longest_2char_seq(str):
    start_pos = end_pos = 0
    charmap = {}
    maxstr = ''
    strlen = len(str)
    while end_pos < strlen - 1:
        while len(charmap) < 3 and end_pos < strlen:
            if not charmap.get(str[end_pos]):
                charmap[str[end_pos]] = 0
            end_pos += 1
        end_pos -= 1
        if len(maxstr) < len(str[start_pos:end_pos ]):
            maxstr = str[start_pos:end_pos]
        charmap = {}
        start_pos = end_pos - 1
        while start_pos > 0 and str[start_pos] != str[end_pos - 1]:
            start_pos -= 1
    return maxstr

public class SubSequence {

   public static void main(String[] args) {
      findLongestSubsequence("aabbaabbaabbaabababa");
      findLongestSubsequence("aabbcbbbadef");
      findLongestSubsequence("aabaadddddaa");
      findLongestSubsequence("aabaacdddddaa");
      findLongestSubsequence("bbbcccbbbbcccca");
   }


   static void findLongestSubsequence(String input) {
      // make validations for null and length 1 strings here
      int initial = 0, changed = 0;
      char firstChar = input.charAt(0), secondChar = input.charAt(1);
      
      firstChar = input.charAt(0);
      String subSequence = "";
      for (int i = 0; i < input.length() - 1; i++) {
         char current = input.charAt(i);
         char next = input.charAt(i + 1);
         // It may be xyx or xyz
         if (current != next) {        
            //End of current sequence
            if(next != firstChar && next != secondChar){
               String currentSequence = input.substring(initial,i+1);
               if(currentSequence.length() > subSequence.length()){
                  subSequence = currentSequence;
               }
               //Re initialize the sequence               
               initial = changed;
               firstChar = current;
               secondChar = next;
            }
            //From next character we can restart
            changed = i+1;
         }
      }
      //If subsequence ends at last
      if(changed <= input.length()-1){
         String currentSequence = input.substring(initial,input.length());
         if(currentSequence.length() > subSequence.length()){
            subSequence = currentSequence;
         }   
      }
      
      System.out.println(subSequence);

   }
}

# Logic : track two characters upto that position
dynamic programming

O(N)

char* long_substring(int input[], int l) {
    char *a1 = malloc(sizeof(char*l+char));
    char *a2 = malloc(sizeof(char*l+char));
    int *r = malloc(sizeof(int*l+int));

    for(i=1;i<=l;i++) {
        if(input[i-1] == a1[i] || input[i-1] == a2[i]) 
            r[i] = r[i] + 1;
        else {
            j = i - 1;
            ch = (i-2)>=0 ? input[i-2] : '';
            count = 1;
            while (j>0) {
                if (ch == a1[j] || ch == a2[j]) 
                    ++count;
                else {
                    j = 0;
                    if(ch != a1[i-1]) 
                        a1[i] = ch;
                    else 
                        a2[i] = ch;
                    r[i] = count;    
                }                
                --j;
            }
        }           
    }
}

public class Substring {
	 public static void main(String[] args)
	  {
	   Substring sub= new Substring();
		 String s="bbbbbbbbbbcccccccccddddeeeeee";
	   String c = sub.substring(s);

	    System.out.println("New String is "+c);
}

public String substring(String s)
{String g = null;
	char c = 0;int r=0;
	for(int i=0;i<s.length();++i)
	{ 
	if(s.charAt(i)!=s.charAt(i+1))
	{
		r++;
		if(r==1)
			c=s.charAt(i);
		if(r>1&&c!=s.charAt(i))
		{ 
		g=s.substring(0, i+1);
			break;
		}
	}
	
	}
	return g;
}

I use a HashMap instead to keep track of the 2 characters (and their frequencies) so far. Basically iterate through the string and either increment the count for an existing character, or determine that we now have more than 2 unique characters. In the latter case, keep advancing the "start" pointer until we have only 2 unique characters in the HashMap again.

static String longest(String s) {
	int positions[] = new int[2];
	int max = 0;
	int len = s.length();
	int start = 0;
	HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
	for(int i=0; i<len; i++) {
		char ch = s.charAt(i);
		if(freq.containsKey(ch)) {
			freq.put(ch, freq.get(ch) + 1);
		} else {
			freq.put(ch, 1);
			while(freq.size() > 2) {
				ch = s.charAt(start++);
				if(freq.get(ch) == 1)
					freq.remove(ch);
				else freq.put(ch, freq.get(ch) - 1);
			}
		}
		if(i-start+1 > max) {
			max = i-start+1;
			positions[0] = start;
			positions[1] = i;
		}
	}
	return s.substring(positions[0], positions[1]+1);
}

It can be easily done by automata and set theory.

Can someone tell me whether this code misses any corner cases....??...Thanks in advance

#include <iostream>
#include <climits>
#include <cstring>
using namespace std;

int main() {
	
	
	char arr[] = "aabbcbbbadef ";
	
	char c1,c2;
    int count1,count2,maxcount=INT_MIN,i;
	c1 = arr[0];count1=1;
	c2 = '1';count2=0;
	
	for(i=1;i<strlen(arr);i++)
	{
		if(arr[i] == c1)
		count1++;
		
		else if(arr[i]!=c1 && c2 == '1')
		{
			c2 = arr[i];
			count2=1;
		}
		
		else if(arr[i]!=c1 && arr[i]==c2)
		{
			count2++;
		}
		
		else
		{
			
			if(count1 + count2 > maxcount)
			maxcount = count1+count2;
			
			char temp_hold_c2 = arr[i-1];
			int temp_hold_count = 0;
			
			int j = i-1;
			
			while(arr[j] == temp_hold_c2)
			{
				temp_hold_count++;
				j--;
			}
			
			c1 = temp_hold_c2;
			count1 = temp_hold_count;
			
			c2 = arr[i];
			count2 = 1;
			
		}
	}
	
	if(count1 + count2 > maxcount)
	maxcount = count1+count2;
	
	if(count2 == 0 && c2 == '1')
	cout<<"Not a valid string"<<endl;
	
	else
	cout<<"maxcount is "<<maxcount;
	return 0;
}

just use two index, complexty O(2n)

int main()
{
    std::string to_test = "aabbcbbbadef";
    if(to_test.length() <= 2)
	return to_test.length();

    int alp_cnt[256] = {0};
    for(int i = 0; i < 256; i++)
    {
        alp_cnt[i] = 0;
    }
    char first, second;
    first = second = to_test[0];
    alp_cnt[first] += 1;
    int max = 0, cur = 1;
    int j = 0;
    int end_index = 0;
    for(int i = 1; i < to_test.length();i++)
    {
        if(to_test[i] == first)
        {
            alp_cnt[first]++;
            cur++;
        }
        else if(to_test[i] == second)
        {
            alp_cnt[second]++;
            cur++;
        }
        else
        {
            if(first == second)
            {
                second = to_test[i];
                alp_cnt[second]++;
                cur++;
                continue;
            }
            if(max < cur)
            {
                max = cur;
                end_index = i-1;
            }
            while(j < i)
            {
                cur--;
                if(--alp_cnt[to_test[j]] == 0)
                {
                    if(to_test[j] == first)
                    {
                        first = to_test[i];
                        alp_cnt[first]++;
                    }
                    else
                    {
                        second = to_test[i];
                        alp_cnt[second]++;
                    }
                    cur++; 
                    j++;
                    break;
                }
                j++;
            }
        }
}
if(max == 0)
{
	max = cur;
	end_index = to_test.length()-1;
}

std::string res;
res.insert(0, to_test, end_index-max+1, max);
    cout<<max<<" "<<end_index<<endl;
}

#include <iostream>
#include <cstring>
using namespace std;

int twochar(string str)
{
int cnt=0;
int hsh[26];
memset(hsh, 0, sizeof(hsh));
int bg=0;
int re=0;

for(int i=0; i<str.size(); i++)
{
int x=str[i]-'a';

if(hsh[x]==0)
{
cnt++;
if(cnt>2)
{
re = max(re, i-bg);
while(--hsh[str[bg]-'a']>0) bg++;
bg++;
cnt--;

}
}

hsh[x]++;
}
return re;
}
int main()
{
string str="aabbcbbbadef";
cout<<twochar(str)<<endl;
return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int twochar(string str)
{
int cnt=0;
int hsh[26];
memset(hsh, 0, sizeof(hsh));
int bg=0;
int re=0;

for(int i=0; i<str.size(); i++)
{
int x=str[i]-'a';

if(hsh[x]==0)
{
cnt++;
if(cnt>2)
{
re = max(re, i-bg);
while(--hsh[str[bg]-'a']>0) bg++;
bg++;
cnt--;

}
}

hsh[x]++;
}
return re;
}
int main()
{
string str="aabbcbbbadef";
cout<<twochar(str)<<endl;
return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int twochar(string str)
{
int cnt=0;
int hsh[26];
memset(hsh, 0, sizeof(hsh));
int bg=0;
int re=0;

for(int i=0; i<str.size(); i++)
{
int x=str[i]-'a';

if(hsh[x]==0)
{
cnt++;
if(cnt>2)
{
re = max(re, i-bg);
while(--hsh[str[bg]-'a']>0) bg++;
bg++;
cnt--;

}
}

hsh[x]++;
}
return re;
}
int main()
{
string str="aabbcbbbadef";
cout<<twochar(str)<<endl;
return 0;
}

Java Implementation:

public static void findLongestStringWithTwoUniqueCharacters(char[] c)
	{
		char c1 = c[0], c2 = '1';
		int sp1 = 0, ep1 = 0;
		int sp2 = -1, ep2 = -1;
		int len = 0;
		int maxLen = -1;
		int fep1 = 0, fep2 = 0, fsp1 = 0, fsp2 = 0;
		char fc1 = 0, fc2 = 0;
		for (int i = 0; i < c.length; i++)
		{
			if (c[i] == c1 && c2 == '1')
			{
				ep1 = i;
				len++;
			}
			else if (c[i] != c1 && c2 == '1')
			{
				c2 = c[i];
				sp2 = ep2 = i;
				len++;
			}
			else if (c[i] == c2)
			{
				ep2 = i;
				len++;
			}
			else if (c[i] == c1)
			{
				len++;
				char tempC = c1;
				c1 = c2;
				c2 = tempC;

				int temp = sp1;
				sp1 = sp2;
				sp2 = temp;

				temp = ep1;
				ep1 = ep2;
				ep2 = temp;

				ep2 = i;
			}
			else if (c[i] != c1 && c[i] != c2)
			{
				if (maxLen < len)
				{
					maxLen = len;
					fep1 = ep1;
					fsp1 = sp1;
					fsp2 = sp2;
					fep2 = ep2;
					fc1 = c1;
					fc2 = c2;
				}

				char tempC = c1;
				c1 = c2;
				c2 = tempC;

				int temp = sp1;
				sp1 = sp2;
				sp2 = temp;

				temp = ep1;
				ep1 = ep2;
				ep2 = temp;

				c2 = c[i];
				sp2 = ep2 = i;

				int j = ep1;
				len = 1;

				while (c[j] == c1)
				{
					sp1=j;
					len++;
					j--;
				}
			}
		}

//		System.out.println("MaxLen: " + maxLen);
//		System.out.println("char 1:" + fc1 + " From and to: " + fep1 + "," + fsp1);
//		System.out.println("char 2:" + fc2 + " From and to: " + fep2 + "," + fsp2);

		prinSolution(c, fsp1, fsp2, fep1, fep2, maxLen);
	}

	private static void prinSolution(char[] c, int fsp1, int fsp2, int fep1, int fep2, int maxLen)
	{
		int start = fsp1 > fsp2 ? fsp2 : fsp1;
		int end = fep1 > fep2 ? fep1 : fep2;
		System.out.println("Input : " + String.valueOf(c));
		System.out.print("Output: ");
		for (int i = start; i <= end; i++)
		{
			System.out.print(c[i]);
		}

		System.out.println();
		System.out.println("MaxLen: " + maxLen);

		System.out.println("-----------------------------------------");

	}

String s=sc.next();
int k=sc.nextInt();

String s1="";
HashMap  <Character,Integer> hm;




for(int i=0;i<s.length();i++){
	s1="";
	hm=new HashMap <Character,Integer> ();

//	System.out.println("value of i is " + i);
	for(int j=i;j<s.length();j++)
	{
  //      System.out.println("ruc");
		if(hm.size()<=k &&!hm.containsKey(s.charAt(j)))
		{
			hm.put(s.charAt(j),1);
			s1+=s.charAt(j);
			
            if(s1.length()>=k&&hm.size()==k)
                 System.out.println(s1);
            
            continue;
		}
		if(hm.containsKey(s.charAt(j)))
        {
				s1+=s.charAt(j);
                  }

             if(hm.size()==k)
              System.out.println(s1);


                


		 if(hm.size()==k && !hm.containsKey(s.charAt(j)))
		{	System.out.println(s1);
			break;
        }

                  
				

			
	}
}

String s=sc.next();
int k=sc.nextInt();

String s1="";
HashMap  <Character,Integer> hm;




for(int i=0;i<s.length();i++){
	s1="";
	hm=new HashMap <Character,Integer> ();

//	System.out.println("value of i is " + i);
	for(int j=i;j<s.length();j++)
	{
  //      System.out.println("ruc");
		if(hm.size()<=k &&!hm.containsKey(s.charAt(j)))
		{
			hm.put(s.charAt(j),1);
			s1+=s.charAt(j);
			
            if(s1.length()>=k&&hm.size()==k)
                 System.out.println(s1);
            
            continue;
		}
		if(hm.containsKey(s.charAt(j)))
        {
				s1+=s.charAt(j);
                  }

             if(hm.size()==k)
              System.out.println(s1);


                


		 if(hm.size()==k && !hm.containsKey(s.charAt(j)))
		{	System.out.println(s1);
			break;
        }

                  
				

			
	}
}

String s=sc.next();
int k=sc.nextInt();

String s1="";
HashMap  <Character,Integer> hm;




for(int i=0;i<s.length();i++){
	s1="";
	hm=new HashMap <Character,Integer> ();

//	System.out.println("value of i is " + i);
	for(int j=i;j<s.length();j++)
	{
  //      System.out.println("ruc");
		if(hm.size()<=k &&!hm.containsKey(s.charAt(j)))
		{
			hm.put(s.charAt(j),1);
			s1+=s.charAt(j);
			
            if(s1.length()>=k&&hm.size()==k)
                 System.out.println(s1);
            
            continue;
		}
		if(hm.containsKey(s.charAt(j)))
        {
				s1+=s.charAt(j);
                  }

             if(hm.size()==k)
              System.out.println(s1);


                


		 if(hm.size()==k && !hm.containsKey(s.charAt(j)))
		{	System.out.println(s1);
			break;
        }

                  
				

			
	}
}