Google Interview Question
Java DevelopersCountry: United States
To get the actual max unique string as is expected here, I am using below method:
public static String longestUniqueChars(Iterator<Character> chars) {
if (chars == null) {
return null;
}
int startUnique = 0;
int curr = 0;
int maxUniqueLength = 0;
int currUniqueLength = 0;
String uniqueString = "";
String maxUniqueString = null;
int[] lastCharIndex = new int[26];
for (int i = 0; i < 26; i++) {
lastCharIndex[i] = -1;
}
while (chars.hasNext()) {
char ch = chars.next();
uniqueString += ch;
if (lastCharIndex[ch - 'a'] == -1 || lastCharIndex[ch - 'a'] < startUnique) {
currUniqueLength++;
} else {
startUnique = lastCharIndex[ch - 'a'] + 1;
currUniqueLength = curr - startUnique + 1;
int indexOfRepChar = uniqueString.indexOf(ch);
uniqueString = uniqueString.substring(indexOfRepChar + 1, uniqueString.length());
}
if (currUniqueLength > maxUniqueLength) {
maxUniqueLength = currUniqueLength;
maxUniqueString = uniqueString;
}
lastCharIndex[ch - 'a'] = curr;
curr++;
}
return maxUniqueString;
}
Tested with following string "abcacdefghijkklabcdefghijklmnoabc" and it gave expected answer which is "abcdefghijklmno"
a c++ code:
int longestSub(string& s)
{
int index[26], len = 0, max=0;
for (int i = 0; i < 26; i++)
index[i]=-1;
for (int i = 0; i < s.size(); i++)
{
int id = tolower(s[i]) - 'a';
if (index[id] != -1)
{
//reset
if (max < len)
max = len;
len = i - index[id];
index[id] = i;
}
else
{
index[id] = i;
len++;
}
}
if (max < len)
max = len;
return max;
}
}
- ashu1.220791 January 18, 2018