Google Interview Question
SDE1sCountry: India
Complexity of this case??
aabcbcbcbcbcbcbcbcbcbcbbccbaa
I might not be getting your algo correctly... can you explain it in some simpler way??
Slightly simplified version:
void findLongestSubString(String str) {
char[] c = str.toCharArray();
int maxLen = -1; int maxStartIndex = -1;
int startIndex = 0;
int Char1LastUniqueIndex = 0;
int Char2LastUniqueIndex = -1;
for(int i =0;i<c.length;i++) {
if(c[i] == c[Char1LastUniqueIndex]) {
Char1LastUniqueIndex = i;
}else if ( Char2LastUniqueIndex == -1) {
Char2LastUniqueIndex = i;
}else if(c[i] == c[Char2LastUniqueIndex]){
Char2LastUniqueIndex = i;
} else {
int len = i - startIndex;
if (len > maxLen) { maxLen = len; maxStartIndex = startIndex; }
//choose the next startIndex
if(Char1LastUniqueIndex > Char2LastUniqueIndex) {
startIndex = Char2LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}else {
startIndex = Char1LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}
}
}
if (maxLen != -1) {
System.out.printf("MaxSubstring = %s, Len=%d", str.subSequence(maxStartIndex, maxStartIndex + maxLen), maxLen);
}
}
@VJ @cerberuz
To handle the case where the string ends with the longest seq, here is the fixed code ( added the i==c.length-1 condition ).
public static void findLongestSubString(String str) {
char[] c = str.toCharArray();
int maxLen = -1; int maxStartIndex = -1;
int startIndex = 0;
int Char1LastUniqueIndex = 0;
int Char2LastUniqueIndex = -1;
for(int i =0;i<c.length;i++) {
if(c[i] == c[Char1LastUniqueIndex]) {
Char1LastUniqueIndex = i;
}else if ( Char2LastUniqueIndex == -1) {
Char2LastUniqueIndex = i;
}else if(c[i] == c[Char2LastUniqueIndex]){
Char2LastUniqueIndex = i;
} else {
int len = i - startIndex;
if (len > maxLen) { maxLen = len; maxStartIndex = startIndex; }
//choose the next startIndex
if(Char1LastUniqueIndex > Char2LastUniqueIndex) {
startIndex = Char2LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}else {
startIndex = Char1LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}
}
if(i==c.length-1){
int len = i - startIndex + 1;
if (len > maxLen) { maxLen = len; maxStartIndex = startIndex; }
}
}
if (maxLen != -1) {
System.out.printf("MaxSubstring = %s, Len=%d", str.subSequence(maxStartIndex, maxStartIndex + maxLen), maxLen);
}
}
@VJ
to handle the case where the strings end with the longest seq
public static void findLongestSubString(String str) {
char[] c = str.toCharArray();
int maxLen = -1; int maxStartIndex = -1;
int startIndex = 0;
int Char1LastUniqueIndex = 0;
int Char2LastUniqueIndex = -1;
for(int i =0;i<c.length;i++) {
if(c[i] == c[Char1LastUniqueIndex]) {
Char1LastUniqueIndex = i;
}else if ( Char2LastUniqueIndex == -1) {
Char2LastUniqueIndex = i;
}else if(c[i] == c[Char2LastUniqueIndex]){
Char2LastUniqueIndex = i;
} else {
int len = i - startIndex;
if (len > maxLen) { maxLen = len; maxStartIndex = startIndex; }
//choose the next startIndex
if(Char1LastUniqueIndex > Char2LastUniqueIndex) {
startIndex = Char2LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}else {
startIndex = Char1LastUniqueIndex + 1;
Char1LastUniqueIndex = startIndex;
Char2LastUniqueIndex = i;
}
}
if(i==c.length-1){
int len = i - startIndex + 1;
if (len > maxLen) { maxLen = len; maxStartIndex = startIndex; }
}
}
if (maxLen != -1) {
System.out.printf("MaxSubstring = %s, Len=%d", str.subSequence(maxStartIndex, maxStartIndex + maxLen), maxLen);
}
}
def findlongest2uniq(str):
if len(str) == 0 or len(str) == 1:
print "invalid string"
return
res = ''
start = 0
end = 0
temp_start = 0
temp_end = 0
chars = [str[0]]
next_temp_start = 0
last_seen_char = str[0]
while temp_end<len(str):
if not(str[temp_end] in chars):
if len(chars) == 2:
temp_start = next_temp_start
chars = chars[1:]
chars.append(str[temp_end])
else:
chars.append(str[temp_end])
if not(str[temp_end] == last_seen_char):
next_temp_start = temp_end
if temp_end - temp_start > end - start and len(chars) == 2:
start = temp_start
end = temp_end
last_seen_char = str[temp_end]
temp_end = temp_end + 1
print str[start:end+1]
findlongest2uniq('aabbcbbbadef')
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;
}
}
The above doesn't correctly handle the following aabaacdddddaa. The below code resolves the above bug.
public class Questions {
public static void main(String[] args) {
//String input = "aabbcbbbadef";
//String input = "aabcbcbcbcbcbcbcbcbcbbccbaa";
String input = "aabaadddddaa";
String result = longestSubstringContaining2Characters(input);
System.out.println("Longest subString for '" + input + "' is '" + result + "'");
}
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;
}
// handles the case where the first character is seen again after the second character, example aabbaa
if (secondCharacter != null && currentCharacter != secondCharacter && currentCharacter == firstCharacter) {
firstCharacter = secondCharacter;
secondCharacter = currentCharacter;
secondCharacterIndex = i;
}
if ((secondCharacter != null) && ((i == input.length() - 1) || (currentCharacter != firstCharacter && currentCharacter != secondCharacter) ) ) {
String currentSubString;
if (i == input.length() - 1) {
currentSubString = input.substring(firstCharacterIndex);
} else {
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;
}
Missed out important case of "bbbcccbbbbcccca"
char* FindMax(const char* s)
{
vector<pair<char, unsigned> > v;
unsigned len = strlen(s);
if (len < 2) return strdup(s);
char c = s[0];
v.push_back(make_pair(c, 0));
for (int i=1; i<len; i++) {
if (s[i] == c) continue;
v.push_back(make_pair(s[i],i));
c = s[i];
}
v.push_back(make_pair(0, len));
if (v.size() < 3) return strdup(s);
char c1 = v[0].first;
char c2 = v[1].first;
int ci1, ci2;
int i1 = ci1 = v[0].second;
int i2 = ci2 = v[2].second;
int cmax = i2 - i1;
int max = cmax;
for (int i=2; i < v.size()-1; i++) {
if (v[i].first == c1) {
ci2 = v[i+1].second;
} else {
ci1 = v[i-1].second;
ci2 = v[i+1].second;
}
cmax = ci2 - ci1;
c1 = c2;
c2 = v[i].first;
if (max < cmax) {
max = cmax;
i1 = ci1;
i2 = ci2;
}
}
return strdup(string(s, i1, i2).c_str());
}
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]
With a simple change, each char is examined only once, as well as each substring with at most 2 char is examined only once (as before)
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]
Each char is examined only once:
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]
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]
With a little change, char are examined only once
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]
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);
}
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;
}
}
}
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
}
- Cerberuz April 14, 2013