Clean Power Research Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
def longest_substr_with_uniq_char(str)
return "" if (str.size == 0)
splits = str.split("")
uniq_char_str = splits[0]
longest = uniq_char_str
splits[1..-1].each do |ch|
if (!uniq_char_str.include?(ch))
uniq_char_str << ch
else
uniq_char_str = ch
end
if (uniq_char_str.length > longest.length)
longest = uniq_char_str
end
end
longest
end
public int lengthOfUniqueSubstring(String s) {
if(s.length() == 0) return 0;
// assuming ASCII characters
boolean[] alphabet = new boolean[256];
int c = 0;
int lastMax = 0;
for (int i = 0; i < s.length(); i++) {
if(alphabet[s.charAt(i)] == false){
alphabet[s.charAt(i)] = true;
c++;
} else {
if(lastMax < c) lastMax = c;
c = 0;
alphabet = new boolean[256];
i--;
continue;
}
}
return (lastMax<c)?c:lastMax;
}
you can not just reset the counter every time you find a repetition, because you just miss everything after the first occurrence, example:
input: 35245176890
solution: 245176890
your solution: 5176890
This solution keeps a map of the last occurrence of each letter and watches the subset's length from the position of the last duplicate (start of new subset).
public static int returnLongestUniqueSubset (String input)
{
//create hashmap to track last occurrence of each letter
HashMap<Character, Integer> letters = new HashMap<Character, Integer>();
int maxLength = 0;
int lastDup = 0; //position of last duplicate seen
for (int i=0;i<input.length();i++)
{
//if letter hasn't been seen before, put its position in hm
if(!letters.containsKey(input.charAt(i)))
{
letters.put(input.charAt(i), i);
}
//if it has been seen, update last duplicate to current pos and re-enter item in hm
else
{
lastDup = i;
letters.put(input.charAt(i), i);
}
//check to update max length
if (maxLength < i-lastDup+1)
{
maxLength = i-lastDup+1;
}
}
System.out.println(maxLength);
return maxLength;
}
runtime: O(n)
in action here: https://ideone.com/9CB7he
There are two tasks to be solved: first, mark occurence of character in a substring and second, scan the whole string while tracking the maximum lenght.
(i) Assuming that the string was ASCII one can use a boolean array of the size 128 in order to mark characters present in a substring.
(ii) We can use two array indexes defining the substring, 'left' and 'right' both starting at position zero. Both indexes can only increment at the time. When 'right' index increments, the new character is added to the substring and marked as present in via boolean array. If the left index increments a character is removed from a substring and unmarked in boolean array.
(iii) The last question is how do we increment indexes. Check char at 'right' and if not present, mark it and increment 'right'. However, if char at 'right' is present, increment unmark char at 'left' and increment.
A sample code is shown below:
public int maxlenSubstring(String s) {
int N = s.length();
int maxlen = 0;
boolean[] h = new boolean[128]; // ASCII, java inits to false
for (int k = 0, i = 0, j = 0; i < N; k++) {
if (!h[s.charAt(i)]) h[s.charAt(i++)] = true;
else h[s.charAt(j++)] = false;
if(maxlen < i-j) maxlen = i-j;
}
return maxlen;
}
Below solution takes O(n) time.
static int longestUniqueSubString(String s){
int length = 0;
if(s==null || (length = s.length())==0)
return 0;
int startIndex = 0,subStringLength=0;
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if(map.containsKey(c) && map.put(c, i) >= startIndex){
if((i-startIndex) > subStringLength){
subStringLength=(i-startIndex);
}
startIndex = i;
}
else{
map.put(c, i);
}
}
// if all characters are unique
if(subStringLength==0){
subStringLength= s.length();
}
return subStringLength;
}
Step 1: Maintain a 256 integer array to store position of last visited character.
Step 2: start from beginning. Check last visited position of char in array.
Step 3: if position is less than the start it means the char is not found in current substring so continue
Step 4: Is position is more than start from there
private static void longestSubstr(String string) {
// TODO Auto-generated method stub
if(string == null || string.trim().length() <=0){
return;
}
Queue<Integer> lenQ = new LinkedList();
int[] placeSet = new int[256];
int start =0;
int len =1;
for(int i=0;i<string.length();i++){
if(placeSet[string.charAt(i)] < start) {
placeSet[string.charAt(i)] =i;
} else {
start = placeSet[string.charAt(i)]+1;
placeSet[string.charAt(i)] = i;
}
if((i-start+1) > len) {
len = i-start+1;
lenQ.clear();
lenQ.add(start);
} else if((i-start+1) == len){
lenQ.add(start);
}
}
while(!lenQ.isEmpty()){
int startStr = lenQ.remove();
System.out.println(" longest String : "+startStr +" length "+len);
for(int i=0;i<len;i++)
System.out.print(string.charAt(startStr+i));
}
return ;
}
public void longestSubstring(string str1)
{
if(str1.Length < 1)
{
Console.WriteLine("string is empty");
return;
}
// to store the previous character index value
int[] characterIndex = new int[256];
int maxlength, startMaxIndex,currentIndex,lastMaxIndex ;
maxlength = startMaxIndex = currentIndex = lastMaxIndex = 0;
while(currentIndex < str1.Length)
{
// To set the uquine character condition
bool[] isRepeat = new bool[256];
int count, start, last, j;
last = count = 0;
start = j = currentIndex;
bool repeatresult = false;
// Condition to verify substring with unqiue characters
while (!repeatresult && j <= str1.Length -1)
{
if (j == str1.Length - 1)
currentIndex = j+1;
int charvalue = str1[j];
//condition Verifying the unqiue character
if (isRepeat[charvalue] == false )
{
// update index value where the character is seen in string
characterIndex[charvalue] = j;
isRepeat[charvalue] = true;
last = j; // tracking the last character position in current loop
count++; // tracking the count of unqiue characters
j++;
}
else
{
// setting the current index value to the previous occurance of the non-unqiue character for search of next unqiue sub string
currentIndex = characterIndex[charvalue] + 1;
characterIndex[charvalue] = j;
last = j - 1; // tracking the last unique character position in current loop
repeatresult = true;
}
}
// check for max lenght
if (count > maxlength)
{
// setting the max length sub string index value
maxlength = count;
startMaxIndex = start;
lastMaxIndex = last;
}
}
//Print the sub string
Console.WriteLine(" SubString Max length = {0} ", maxlength);
while (startMaxIndex <= lastMaxIndex)
{
Console.Write(str1[startMaxIndex]);
startMaxIndex++;
}
}
object LongestUniqueSubstring {
val input = "aaabcaaabded"
def main(args: Array[String]) {
println(lus(input))
}
def lus(s: String) = {
var maxSubstring = ""
for (i <- 0 until s.length) {
val longestPrefix = lup(s.substring(i))
if (maxSubstring.length < longestPrefix.length) {
maxSubstring = longestPrefix
}
}
maxSubstring
}
//longest unique chars prefix
var lubArr: Array[Boolean] = null
private def lup(s: String): String = {
lubArr = new Array[Boolean](256)
var index = 0
var ret = new StringBuilder()
while (index < s.length) {
if (!lubArr(s.charAt(index))) {
ret.append(s.charAt(index))
lubArr(s.charAt(index)) = true
index += 1
} else {
return ret.toString
}
}
return ret.toString
}
}
Keep a map storing the last occurrence of each character in the original sequence.
Whenever you stumble upon a character that is already present in the subsequence you are considering, reset the start position of the subsequence to the index right after the last occurrence of this conflicting character.
Every time you find a character that can be added to the subsequence, check if the new length is better than the best length so far.
#include <string>
#include <map>
int longest(const std::string &word)
{
if (word.empty()) return 0;
std::map<char, int> last_occurrence;
for (const char &c: word) {
last_occurrence[c] = -1;
}
int i, start = 0, length = 1, best_length = 1;
last_occurrence[word[0]] = 0;
int n = word.length();
for (i = 1; i < n; ++i) {
int c = word[i];
int lo = last_occurrence[c];
if (lo >= start) {
start = lo + 1;
length = i - start + 1;
}
else {
++length;
if (length > best_length)
best_length = length;
}
last_occurrence[c] = i;
}
return best_length;
}
- Sathya January 29, 2015