Amazon Interview Question for SDE-2s


Team: Cyllas Experience
Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
10
of 12 vote

public static String longestSubstringUnrepeatedChar(String inputString) {
        String longestSoFar = "";
        String longestSubstringResult = "";
        if (inputString.isEmpty()) {
            return "";
        }
        if (inputString.length() == 1) {
            return inputString;
        }
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < inputString.length(); i++) {
            char currentCharacter = inputString.charAt(i);
            if (longestSoFar.indexOf(currentCharacter) == -1) {
                if (!map.containsKey(currentCharacter)) {
                    map.put(currentCharacter, i);
                }
                longestSoFar = longestSoFar + currentCharacter;
            } else {
                longestSoFar = inputString.substring(map.get(currentCharacter) + 1, i + 1);
                map.put(currentCharacter, i);
            }
            if (longestSoFar.length() > longestSubstringResult.length()) {
                longestSubstringResult = longestSoFar;
            }
        }
        return longestSubstringResult;
    }

- techpanja November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is my program

package com.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

public class TestMe {

public static void main(String[] args) {

ArrayList<Integer> list = getInput();

HashMap<Integer, Integer> map = new HashMap<>();

Iterator<Integer> iterator = list.iterator();

int count = 0;
int maxCount = 0;

while (iterator.hasNext()) {
Integer key = iterator.next();

if (!map.containsKey(key)) {
map.put(key, 1);
count ++;
} else {
//count--;
}

if (count > maxCount) {
maxCount = count;
}
}

System.out.println("----------Max Length is ---------->" + maxCount);

}



private static ArrayList<Integer> getInput() {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(1);
list.add(2);
list.add(3);
list.add(1);
list.add(2);
return list;
}

}

- Manish Narula November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is my working program

package com.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

public class TestMe {
	
	public static void main(String[] args) {
		
		ArrayList<Integer> list = getInput();
		
		HashMap<Integer, Integer> map = new HashMap<>();
		
		Iterator<Integer> iterator = list.iterator();
		
		int count = 0;
		int maxCount = 0;
		
		while (iterator.hasNext()) {
			Integer key = iterator.next();
			
			if (!map.containsKey(key)) {
				map.put(key, 1);
				count ++;
			} else {
				//count--;
			}
			
			if (count > maxCount) {
				maxCount = count;
			}
		}		
		
		System.out.println("----------Max Length is ---------->" + maxCount);		
		
	}
	
	
	
	private static ArrayList<Integer> getInput() {		
		ArrayList<Integer> list = new ArrayList<>();
		list.add(1);
		list.add(2);
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(1);
		list.add(2);		
		return list;
	}

}

- Manish Narula November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

There is no need to consume O(n) space by using hashtable. Use fixed size array instead as characters are limited.

public static String longestNonDupSubstr(String str)
{
	String longestSoFar;
	String longestSubStr;
	char current;
	int lastSeen[256];
	for(int i=0; i<256; i++)
		lastSeen[i] = -1;

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

		if(lastSeen[current] == -1)
			longestSoFar = longestSoFar + current;
		else 
			longestSoFar = str.substring(lastSeen[current]+1, i+1);
		
		lastSeen[current] = i;

		if(longestSoFar.length() > longestSubstr.length())
			longestSubStr = longestSoFar;
	}
	return longestSubStr;
}

- zahidbuet106 December 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not working for some example. There is a bug!

//For example
 String str = "abcabaabccfdsaewer"; //Should return "cfdsaew", but returns "abaabccfds"

- Doug December 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class MaxSubString
{
public static void main(String[] args)
{
Set<Character> subList = new LinkedHashSet<Character>();
List<Set<Character>> subStrList = new LinkedList<Set<Character>>();
String myStr = "abcdeavbcseabcdeabcsecser";
char[] myStrArray = myStr.toCharArray();
for (char ch : myStrArray)
{
if (!subList.add(ch))
{
subStrList.add(subList);
subList = new LinkedHashSet<Character>();
subList.add(ch);
}
}
subStrList.add(subList);
System.out.println("Max Length:" + getMaxSubStrLength(subStrList));
}

static int getMaxSubStrLength(List<Set<Character>> subStrList)
{
int lenth = 0;
Set<Character> maxSubSet = null;
for (Set<Character> subSet : subStrList)
{
if (subSet.size() > lenth)
{
maxSubSet = subSet;
lenth = subSet.size();
}
for (Character ch : subSet)
{
System.out.print(ch);
}
System.out.println();
}
return maxSubSet.size();
}
}

- VIJAY RAJ April 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@techpanja I think your code wont work on "abcba", it returns abcb which is wrong, answer should be "abc".

- sigkill June 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@techpanja You need to remove elements from your hashmap after a duplicate is found.

- acannon828 February 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

O(1) space O(n) time solution

1. Scan the string from left to right and keep an array for saving position a character last encountered during the scan.
2. While scanning before updating the lastSeen array check if the character already encountered in the current scan so far.
3. If the character was not encountered that means you can add this to the longest SubString found so far.
4. Otherwise the character already encountered in the current scan which means we have encountered a duplicate. So, we ignore the substring from beginning to this position as this makes the future sequence containing duplicates.
5. While calculating longest substring so far encountered keep the tracking for absolute longest one.

public static String longestNonDupSubstr(String str)
{
	String longestSoFar;
	String longestSubStr;
	char current;
	int lastSeen[256];
	for(int i=0; i<256; i++)
		lastSeen[i] = -1;

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

		if(lastSeen[current] == -1)
			longestSoFar = longestSoFar + current;
		else 
			longestSoFar = str.substring(lastSeen[current]+1, i+1);
		
		lastSeen[current] = i;

		if(longestSoFar.length() > longestSubstr.length())
			longestSubStr = longestSoFar;
	}
	return longestSubStr;
}

- zahidbuet106 December 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code should initialize back the lastSeen[256] array to -1 whenever it encoutners else condition of ( lastSeen[current] == -1) so that when checking for subsequent substrings, previous occurrences of alphabets don't interfere with checking, please correct me if I'm wrong.

- Don Corleone October 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

Java solution with O(N) run time and O(1) space complexity.

package careercup;

public class MaxSubstring {
	public static String find(String input) {
		char[] str = input.toCharArray();
		boolean[] charsSoFar = new boolean[26];
		int startIndex = 0;
		int bestStartIndex = 0;
		int bestEndIndex = 0;

		for (int i=0; i < str.length; i++) {
			int charIndex = getCharIndex(str[i]);
			if (!charsSoFar[charIndex]) {
				// keep checking off characters as used
				charsSoFar[charIndex] = true;
			}
			else {
				// this character has already been used in the current substring
				// if current substring is bigger than the current best, update current best
				if (getLength(startIndex, i) > getLength(bestStartIndex, bestEndIndex)) {
					bestStartIndex = startIndex;
					bestEndIndex = i;
				}
				// now scan forwards removing characters from the substring
				//  until this character is free to be used again
				while(charsSoFar[charIndex]) {
					int startCharIndex = getCharIndex(str[startIndex]);
					charsSoFar[startCharIndex] = false;
					startIndex++;
				}
				// the character is now free, mark it as used since the new substring is now using it
				charsSoFar[charIndex] = true;
			}
		}
		return input.substring(bestStartIndex, bestEndIndex);
	}

	private static int getLength(int startIndex, int endIndex) {
		return endIndex - startIndex + 1;
	}

	private static int getCharIndex(char c) {
		return (int)(c - 'a');
	}
}

- shinsetsu November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iteration 0:
------------
 |
"AABC"
window = 0;
sart =0;
i = 0

Iteration 1:
-------------
  |
"AABC"
window = 1; (1 -0)
start = 1; duplicate occurs so move it
i = 1

Iteration 2:
-------------
   |
"AABC"
window = 1;
start = 1; 
i = 2

Iteration 3:
-------------
    |
"AABC"
window = 3; (i - start) +1
start = 1; 
i = 3  // we are reaching end of string so check for last

- Ajeet November 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ajeet, why you fill up the careercup posting by separating all over?
It is annoy people.

-Guest DS

- algos November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yea dude, i also realized that ... actually editing feature has been removed from careercup, so i re-posted it after formatting.

No option to remove junk\wrong one ... :(

- Ajeet November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to windowing solutions suggested in this thread, but a little better then them.

The idea is we do not need to move back the window to previous location of duplicate found in current window. Rather, we can continue from current location without ever moving back. Hence, can attain O(n) in true sense. This is on the lines of Knuth-Pratt-Morris algo.

int MaxLenUniqeCharsSubstr(string str)
{
	map<char, int> win;
	int max = 0, cur = 0;	

	for(int i = 0; i < str.length(); ++i)
	{
		char ch = str.at(i);
		if(win.end() != win.find(ch))
		{
			if(max < cur)
				max = cur;

			RemoveFromMapPosLowerThan(win, ch);
			cur = win.size();
		}
		cur++;
		win[ch] = i;
	}

	return max;
}

void RemoveFromMapPosLowerThan(map<char, int> &win, char ch)
{
	map<char,int>::iterator it = map.begin();
	int pos = win[ch];

	while(it != map.end())
	{
		if(it->second <= pos)
			win.erase(it);
	}
}

- mindless monk November 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mindless monk
I did not get ur point ..."Hence, can attain O(n) in true sense. "
Above solution is also O(N) .. we are not moving back, we are using previous index just for size of window.

Can you explain how is ur solution .. O(N) ... in true sense or with true sense... ? In each iteration you are searching a location in map.

- Ajeet November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ajeet

Lets consider this example.
String: abcdaefgh

Method suggested by you:
after finding duplicate 'a' at position 4, you start comparisons from b

My suggestion:
You do not have to traverse b,c,d again

What you pointed about searching in map, is true. My solution does require you to traverse the map. But even your solution need to call clear on map. So, eventually you are also traversing the map and freeing the memory.

- mindless monk November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mindless monk

I tried to figure out the logc. However, i am not sure if i understand the meaning of

if(win.end() != win.find(ch))

Following is an example, i tired the logic with.

Input - "bcacbbd"

(b) b -> 0 ; cur = 1 ;
(c) max = 1 ; cur = 1 ; cur = 2 ; c -> 1
(a) max = 2 ; cur = 2 ; cur = 3 ; a -> 2
(c) max = 3 ; (pos = 1, erase(b), erase(c)) ; cur = 1 ; cur = 2 ; c -> 3
(b) cur = 2 ; cur = 3 ; b -> 4
(b) cur = 4 ; b -> 5
(d) max = 4 ; .... (incorrect)

Let me know what am i doing wrong.

- aCoder November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mindless monk
Ohhk i got your confusion . Just forgot this line:

"If an duplicate occurs than I just move start position to previous index of this character(Hash table has previous index)".

Editing feature is not available so i cant remove it . It was before modification in my algo. Just follow java implementation and visual representation.

"start pointer is never used to compare. It is "ï"."And as you can see we never go back with "i".
Just try visual representation of this algo .. i posted it using ... AABC".

- Ajeet November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You don't actually need to remove anything from the map. Just keep an index to track the starting position of the current substring and update the map with the last seen index of each character. Now that's true O(n).

- uruk hai November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int maxSizeNoDups(String s) {

int maxSize = 0;


for (int i = 0; i < s.length(); i++) {
int currentSize = 0;

for (int j = i; j < s.length(); j++) {
if (j != i) {
if (s.substring(i, j).contains("" + s.charAt(j)))
break;
}
currentSize++;
maxSize = maxSize > currentSize ? maxSize : currentSize;

}
}

return maxSize;
}

- Anonymous November 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int maxSizeNoDups(String s) {
		
		int maxSize = 0;
		
		
		for (int i = 0; i < s.length(); i++) {
			int currentSize = 0;
			
			for (int j = i; j < s.length(); j++) {
				if (j != i) {
					if (s.substring(i, j).contains("" + s.charAt(j)))
						break;
				}
				currentSize++;
				maxSize = maxSize > currentSize ? maxSize : currentSize;
				
			}
		}
		
		return maxSize;
	}

- Anonymous November 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple O(n²) solution:

public static String find(String s){
        if(s.equals("")) return "";
        if(s == null) return null;
        int max = 0;
        int begin = 0;
        HashSet<Character> found = new HashSet<Character>();
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            //Impossible to find a bigger substring
            if(chars.length - i < max) break;
            found.clear();
            found.add(chars[i]);
            for(int j = i+1; j <= chars.length; j++){
                if(j  == chars.length){
                    int currentRange = j-i;
                    if(currentRange > max){
                        max = currentRange;
                        begin = i;
                    }
                }
                else if(found.contains(chars[j])){
                    int currentRange = j-i;
                    if(currentRange > max){
                        max = currentRange;
                        begin = i;
                    }
                    break;
                }
                else{
                    found.add(chars[j]);
                }
            }
        }
        if(max == 1) return chars[begin] + "";
        return s.substring(begin, begin + max);
    }

- Anonymous November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Now an O(n) time + O(n) space

public static String find2(String s){
        if(s.equals("")) return "";
        if(s == null) return null;
        HashMap<Character, Integer> found = new HashMap<Character,Integer>();
        char[] chars = s.toCharArray();
        int[] maxSoFar = new int[chars.length];
        maxSoFar[0] = 1;
        found.put(chars[0],0);
        for(int i = 1; i < chars.length; i++){
            if(found.containsKey(chars[i])){
                maxSoFar[i] = Math.min(i - found.get(chars[i]), maxSoFar[i-1] + 1);
            }
            else{
                maxSoFar[i] = maxSoFar[i-1] + 1;
            }
            found.put(chars[i],i);
        }

        int maxIndex = maxIndex(maxSoFar);
        return s.substring(maxIndex - maxSoFar[maxIndex] + 1, maxIndex+1);
    }

    public static int maxIndex(int[] arr){
        int max = 0;
        for(int x : arr) max = x > max? x : max;
        for(int i = 0; i < arr.length; i++)
            if(arr[i] == max) return i;
        return -1;
    }

- Anonymous November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package Stringissues;

import java.util.HashMap;
import java.util.Map;

public class StringIssues {
	// Given s string, Find max size of a sub-string, in which no duplicate
	// chars present.
	// String AlphaBetaCharlie
	public static void main(String[] args) {
		String str = "CharliedaadaabcdefghijklmnmbrijeshoAlphaBeta";
		HashMap hm = new HashMap();
		String targetString = str.toLowerCase();
		char[] charArray = targetString.toCharArray();
		int len = charArray.length;
		int stringlength = charArray.length;

		String finalAnswer = "";
		int count, j = 0;
		StringBuilder temp = new StringBuilder();
		String temp1 = new String();
		for (int i = 0; i < len; i++) {
			j = i + 1;

			if ((!hm.containsKey(charArray[i]))
					&& (((stringlength - 1) + j) == len)) {
				hm.put(charArray[i], "");
				temp.append(charArray[i]);

			} else {
				hm.clear();
				if (finalAnswer.length() < temp.length())
					finalAnswer = temp.toString();
				if (temp.length() > 0) {
					temp.setLength(0);
				}

			}
			--stringlength;

		}
		System.out.println(finalAnswer);
	}
}

- brijeshtiwari2020 November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if input string is efabcah123456..then it will not print largest string bcah123456..so hare is bug in this code.

- om kumar November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>

using namespace std;


bool duplicate(string com)
{
	for (int k = 0; k < com.length()-1; ++k)
	{
		for (int z = k+1; z < com.length(); ++z)
		{
			if (com[k] == com[z])
				return true;
		}
	}
	return false;
}


int main()
{
	std::string content = "ALA MA KOTA";
	int s = content.length();
	std::string cur(""), longest("");
	cur += content[0];

	for (int k = 1; k < s; ++k)
	{
		cur += content[k];
		if (!duplicate(cur))
		{
			if (cur.length() > longest.length())
				longest = cur;
		}
		else if (k < s-1)
		{
			cur = "";
			cur += content[k];
		}
	}

	cout << longest << endl;

	system("pause");
	return 0;
}

- And November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution, time complexity O(N) space O(1):

public class SubstringWithUniqueChars {

  public static void main(String[] args) {
    String str = "AABCdefghhijkl";
    System.out.println(str +" -- " +getSubstringWithUniqueChars(str.toCharArray()));
  }// end of main
 
  static final int NOT_FOUND = -1;
  /**
   * Given s string, Find max size of a sub-string, in which no duplicate chars present.
   * @param chars -- 
   * @return maxLength of array without any duplicate characters
   */
  public static int getSubstringWithUniqueChars(char[] chars){
    int maxLen = 1; // the least is 1
    int beginOffset = 0;
    // use byte or short to reduce space
    int[] flags = new int[256];
    java.util.Arrays.fill(flags, SubstringWithUniqueChars.NOT_FOUND);
    
    for(int i = 0; i < chars.length; ++i){
       if(flags[(int)chars[i]] == NOT_FOUND) flags[(int)chars[i]] = i;
       else {
         // found duplicate char

         // Check the max length and update if it is greater than previous
         maxLen = Math.max(i-beginOffset, maxLen);
         // restart count from here
         beginOffset = i;
       }// end of else (flags[i] == NOT_FOUND
    }// end of for(i=0..chars.length)
    
    return maxLen;
  }// end of getSubStringWithUniqueChars

}// end of class SubstringWithUniqueChars

- ashivaru November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops !! duplicate, my bad.

- Anonymous November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you need to reset the flags array whenever the beginOffset is reset to i.
Take an example string of "BAABCdefghhijkl"

- rk November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modified version of your code.

public static int maxLenUniqCharSubStr(String str)
	{
		int[]startEnd = new int[2];
		int[] chars = new int[256];
		int length = str.length();
		int maxLen = 0, begin=0;
		int i=0;
		for (i = 0; i < length; ++i)
		{
			//if the character was found earlier but after the begin index, this means its a duplicate
			if(chars[str.charAt(i)] != 0 && chars[str.charAt(i)] >= begin)
			{
				if(i-begin>maxLen)
				{
					startEnd[0] = begin;
					startEnd[1] = i;
					//System.out.println(str.substring(begin, i));
					maxLen = i-begin;
				}
				begin = chars[str.charAt(i)]+1;
				System.out.println("DEBUG:begin:"+begin+", i:"+i);
			}
			else if(i == length -1)//Last char and not a duplicate therefore need to check if maxLen needs to change
			{
				if(i-begin+1>maxLen)//+1 is for including the last character in the length
				{
					startEnd[0] = begin;
					startEnd[1] = i+1;
					//System.out.println(str.substring(begin, i+1));
					maxLen = i-begin+1;
				}
			}
			chars[str.charAt(i)] = i;
		}
		System.out.println("Max Length:"+maxLen+", max length substring:"+str.substring(startEnd[0],  startEnd[1]));
		return maxLen;
	}

- rk November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// A DP solution.

//Given s string, Find max size of a sub-string, in which no duplicate chars present.

public class StringUtil {

	public static String maxNoDupSubstr(String s)
	{
		if(s.length() == 0 || s == null)
		{
			return s;
		}
		
		// hash map : character -> character's most recent seen index.
		int[] recent = new int[256];
		
		for (int i=0;i<recent.length; i++)
		{
			recent[i] = -1;
		}
	
		// max length end with current character.
		int[] len = new int[s.length()];
		
		len[0] = 1;
		recent[s.charAt(0)] = 0;
		
		int maxSubEnd = 0;
		int maxLen = 1;
		
		
		for( int i = 1; i < s.length(); i++)
		{
			char curChar = s.charAt(i);
			// update len[] for cur index.
			if (recent[curChar] < i - len[i - 1])
			{
				len[i] = len[i-1] + 1;
			}
			else
			{
				len[i] = i - recent[curChar];
			}
			recent[curChar] = i;
			
			//update max len and its index.
			if ( maxLen < len[i])
			{
				maxSubEnd = i;
				maxLen = len[i];
			}
			
		}
		return s.substring(maxSubEnd - maxLen + 1, maxSubEnd + 1);
	}
	
	public static void main(String[] _)
	{
		String s = "";
		System.out.println(s + " : " + maxNoDupSubstr(s));
		
		s = "s";
		System.out.println(s + " : " + maxNoDupSubstr(s));
		
		s = "ss";
		System.out.println(s + " : " + maxNoDupSubstr(s));
		
		s = "sas";
		System.out.println(s + " : " + maxNoDupSubstr(s));
		
		s = "ABCDEBFTR";
		System.out.println(s + " : " + maxNoDupSubstr(s));
		
		s = "abcdefghijklmnopqrstuvwxyz";
		System.out.println(s + " : " + maxNoDupSubstr(s));
		
		s = "abcdeffffffffghijklmnopq";
		System.out.println(s + " : " + maxNoDupSubstr(s));
		
		s = "abcdefcbhjklm";
		System.out.println(s + " : " + maxNoDupSubstr(s));	
	}	
}

- RZ November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

here is the output
:
s : s
ss : s
sas : sa
ABCDEBFTR : CDEBFTR
abcdefghijklmnopqrstuvwxyz : abcdefghijklmnopqrstuvwxyz
abcdeffffffffghijklmnopq : fghijklmnopq
abcdefcbhjklm : defcbhjklm

- rz November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

all these O(1) space, O(strlen) time solutions.... Wow!

Now waiting for O(1) time and space solutions to be posted :P

- S O U N D W A V E November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the characters are a-z, then O(1) space algorithms exist.

############# Go away, troll. ###############

- Subbu. November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I never said they don't exist. "Uruk hai" is not me btw.

bigO notation is a total mess in the comp sci community to begin with. I would like to start a movement to clean it up, firstly by subscripting the O, theta, omega with the variables under consideration always when stating bounds.

So technically, if we consider bigO with _no_ subscripts pertaining to encoding size or alphabet size, then yes there are apparently O(1) space algorithms posted on this thread. Correct.

That is what my post you are responding to you hinted at. Not everyone's bigO is the same. But of course you knew that because you are an ultimate dumbass.

--------------

An important side note:
For these problem usually it is implicit that O, theta, omega consider (are subscripted to consider) encoding size and/or alphabet size.

One very simple reason for this is because these algorithms start off declaring arrays that depend on such things, and such things _can_ vary in size, so excluding these as variables seems unnatural. Another reason is that in some sense string based questions automatically force us, when designing these algorithms you are talking about, to consider these variables. So it would seem unwise to not subscript the O with encoding size and alphabet size.

------
Side side note:
You are too dumb to have practiced to become a dumbass. There has to be more to it.

- Urik November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In other words, to dumb it down more for Subbu and/or Subbu's fan above:

O(1) , Omega(1), Theta(1) are technically meaningless. What is 1 a function of?

For that matter, what is O(n) ?
Normally this means something like O(f(n)) where f(n) = n.
But it could also mean we are considering a function of multiple variables and the bounds being spoken of only depends on one variable (n). Something like, O( f(n,m) ) where f(n,m) = n.

-------

For old time's sake:

"DO THIS ALGORITHM IN O(1) #### AMAZON WILL ASK ### BEST LOGIC ONLY LET'S SEE WHO GET THE O(1)"

- Urik November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Urik. Dumbass.

Have you heard of the unit cost word ram model of computation? If not, go away. If you have indeed heard of it, you are an even bigger idiot than your posts imply.

################# WHAT A MORON ##########################

- Subbu. November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No it is cache oblivious model of computation. Subbu is level 1 troll. Nothing compred to Anonymous.

- Anonymous November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Oblivious anon/Urik/TrollCity:

LOL. You really are clueless, with a very high opinion of yourself. Dipshit.

A cache-oblivious algorithm is essentially a RAM algorithm.

Assuming 8 bit characters, we can in fact, give an O(1) algorithm.

############ WHAT A FUCKING IDIOT ######################

- Subbu. November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i didn't disagree with you on the O(1)
and i'm not uruk hai
and i'm wasn't talking to you about any computational models , nor do I care about ram or cache here

#include <limits.h>
Type  hash[1U<<CHAR_BIT];

Yes, one _can_ consider above as O(1) storage. The storage size is compile time fixed so we can subscript it "off" (i.e., remove it as a variable) from the O notation... sure.

- u. November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@u. Apologies for the identity mistake.

You do need to have an underlying model in mind, before talking about complexity (time/space).

Typically, when the model is not mentioned, the standard assumption is the unit cost word RAM model.

So if you are given a string of length n, the input size is n (n words).

So O(1), O(n^2) etc all make sense.

If you do not have a underlying model in mind, then talking about complexity is nonsense.

- Subbu. November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String longestSubstringUnrepeatedChar(String inputString) {
        String longestSoFar = "";
        String longestSubstringResult = "";
        if (inputString.isEmpty()) {
            return "";
        }
        if (inputString.length() == 1) {
            return inputString;
        }
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < inputString.length(); i++) {
            char currentCharacter = inputString.charAt(i);
            if (longestSoFar.indexOf(currentCharacter) == -1) {
                if (!map.containsKey(currentCharacter)) {
                    map.put(currentCharacter, i);
                }
                longestSoFar = longestSoFar + currentCharacter;
            } else {
                longestSoFar = inputString.substring(map.get(currentCharacter) + 1, i + 1);
                map.put(currentCharacter, i);
            }
            if (longestSoFar.length() > longestSubstringResult.length()) {
                longestSubstringResult = longestSoFar;
            }
        }
        return longestSubstringResult;
    }

- Anonymous November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Requirement:
1. Find Max size of substring with no duplicates.
2. No need to find the substring, just its length.
Have verified with this source string "asdfabb12345hh123456789hh" result=10, pretty much covers boundry conditions.
How this works ?

public static int getMaxSizeSubstringWithNoDupChars(String str)
	{
		ArrayList<Character> s = new ArrayList<Character>();
		int largestSubStringlength = 0;
		char ch;
		for(int i=0;i<str.length();i++)
		{
			ch=str.charAt(i);
			if(s.contains(ch))
			{
				if(largestSubStringlength < s.size())
					largestSubStringlength = s.size();
				s.clear();
				s.add(ch);
			}
			else
				s.add(ch);				
		}
		return largestSubStringlength;
	}

- Hisaravanankesavan November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My updated code,
Requirement:
1. Find Max size of substring with no duplicates.
2. No need to find the substring, just its length.
Have verified with this source string "asdfabb12345hh123456789hh" result=10, pretty much covers boundry conditions.
How this works ?

public static int getMaxSizeSubstringWithNoDupChars(String str)
	{
		ArrayList<Character> s = new ArrayList<Character>();
		int largestSubStringlength = 0;
		char ch;
		for(int i=0;i<str.length();i++)
		{
			ch=str.charAt(i);
			if(s.contains(ch))
			{
				if(largestSubStringlength < s.size())
					largestSubStringlength = s.size();
				s.clear();
				
			}
			s.add(ch);
		}
		if(largestSubStringlength < s.size())
			largestSubStringlength = s.size();
		
		return largestSubStringlength;
	}

- Hisaravanankesavan November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String maxSubStringWithoutDuplicate(String s){
    //    Given s string, Find max size of a sub-string, in which no duplicate chars present.
        if(s==null || s.isEmpty()){
            return s;
        }
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        String max = "";
        int curLen = 0;
        int start = 0;
        for(int i=0; i<s.length(); i++){
            if(map.get(s.charAt(i))==null || map.get(s.charAt(i))==-1 || map.get(s.charAt(i)) <start){
                map.put(s.charAt(i), i);
                curLen++;
                
            }
            else{
                if(curLen > max.length()){
                    max = s.substring(start, start+curLen);
                }
                if(curLen > map.get(s.charAt(i))-i){
                    curLen-= map.get(s.charAt(i))-start;
                    start = map.get(s.charAt(i))+1;

                }
                else{
                    start = i;
                    curLen = 0;
                }
                map.put(s.charAt(i), i);
                
            }
        }
        return max;
        
    }

- meow November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution:

public static int maxSize(String S){

int len = 0;
int maxLen = 1;
HashMap<Character, Integer> theMap = new HashMap<Character, Integer>();

for(int i=0; i < S.length(); i++){

if(theMap.containsKey(S.charAt(i))){
if(maxLen < len){
maxLen = len;
}
theMap.clear();
len=0;
}
else{
theMap.put(S.charAt(i), 1);
len++;
}

}

if(maxLen < len){
maxLen = len;
}

return maxLen;
}

- madhu November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static string MaxSizeSubstringUniqueChars(string input)
{
	if (string.IsNullOrEmpty(input) == true)
	{
		throw new ArgumentNullException("Empty/null string");
	}
	
	Dictionary<char, int> charMap = new Dictionary<char, int>();
	int start = 0;
	string currentSubstring = string.Empty;
	string maxSubstring = string.Empty;
	
	for (int index = 0; index < input.Length; index++)
	{
		char current = input[index];
		
		if (charMap.ContainsKey(current) == false)
		{
			charMap.Add(current, index);
		}
		else
		{
			currentSubstring = input.Substring(start, index - start);
			
			if (currentSubstring.Length > maxSubstring.Length)
			{
				maxSubstring = currentSubstring;
			}
			
			start = charMap[current] + 1;
			index = start - 1;
			charMap.Clear();
		}
		
		if (index + 1 == input.Length)
		{
			currentSubstring = input.Substring(start, input.Length - start);
			if (currentSubstring.Length > maxSubstring.Length)
			{
				maxSubstring = currentSubstring;
			}
		}
	}
	
	return maxSubstring;
}

- Ilker November 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my working code. It works for all the strings given above in comments.


public class DupCheck {



public static void main(String args[])
{
int count=0;
String name = "efabcah123456";
boolean duplicate = false;
int currentLength = 0;
int minIndex = 0;
int maxIndex = 0;
int maxLength = 0;
int currentIndex = 0;
String stringChars = "";

name = name.trim().toLowerCase();

System.out.println("Length = "+stringChars.length());

while(count<name.length()) {

for(int charCount = 0; charCount < stringChars.length();charCount++) {
if(stringChars.charAt(charCount) == name.charAt(count)) {
duplicate = true;
System.out.println("Duplicate char "+name.charAt(count)+" at pos "+(count+1));
break;
}
}

if(!duplicate) {
stringChars += name.charAt(count);
System.out.println("String is "+stringChars);

if(stringChars.length() > (maxIndex-minIndex)) {
maxIndex = currentIndex+stringChars.length();
minIndex = currentIndex;
}


count++;
} else {
count = currentIndex+1;
maxLength = currentLength;

if(stringChars.length() > (maxIndex - minIndex)) {
maxIndex = currentIndex+stringChars.length();
minIndex = currentIndex;
}

currentLength = 0;
currentIndex = currentIndex+1;

duplicate = false;
stringChars = "";

}



}
System.out.println("Sub string with no duplicate letters is "+name.substring(minIndex,maxIndex));

System.out.println("Length of sub string is " + (maxIndex-minIndex));
}
}

- Rajesh Gopalan November 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxSubStringNoDuplicate {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

System.out.println("Ener String");
String str = sc.nextLine();
int limit = 0;
char[] ch ;
ch = str.toCharArray();


for(int i =0;i<ch.length-1;i++){
for(int l=i+1;l>0;l--){
if(l!=0){
if(ch[l-1]==ch[i+1])
limit = i;

}
}

}

System.out.print("Max SubString Wih No Duplicates ");
System.out.println(str.substring(0,limit+1));


}




}

- Kalai November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

net. solution

class LongestText
    {
        public static string FindLongestSubText(string text)
        {
            Dictionary<char, int> positions = new Dictionary<char, int>();
            int[] lengths = new int[text.Length];

            lengths[0] = 1;
            positions.Add(text[0], 0);

            for (int i = 1; i < text.Length; i++)
            {
                char ch = text[i];
                if (!positions.ContainsKey(ch))
                {
                    lengths[i] = lengths[i - 1] + 1;
                }
                else
                {
                    int index = positions[ch];
                    lengths[i] = i - positions[ch];
                }
                positions[ch] = i;
            }

            int maxIndex = lengths.ToList().IndexOf(lengths.Max());

            return new String( text.Skip(maxIndex - (lengths[maxIndex] - 1)).Take(lengths[maxIndex]).ToArray());

        }
    }

- Lapin November 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

$s = "asdfasldghlasdfhlsadkjfhlasdhgaksldjfsdafadsfasdf";

$all_strs = [];

function check($char, $distribution) {
  if (!array_key_exists($char, $distribution)) {
    $distribution[$char] = 1;
    return $distribution;
  }
}

$distributions = [];

for ($i = 0; $i < strlen($s); $i++) {
  $distributions[$i] = [$s[$i] => 1];
  $all_strs[] = $s[$i];
}

$len = 2;
while (!empty($distributions) && $len <= strlen($s)) {
  for ($i = 0; $i < strlen($s) - $len + 1; $i++) {
    if (isset($distributions[$i])) {
      $distribution = check($s[$i+$len-1], $distributions[$i]);
      if ($distribution != null) {
        $all_strs[] = substr($s, $i, $len);
        $distributions[$i] = $distribution;
      }
      else {
        unset($distributions[$i]);
      }
    }
  }
  unset($distributions[strlen($s)-$len+1]);
  $len = $len + 1;
}

var_dump($all_strs);

- Paul November 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ version.

#include <iostream>
#include <unordered_set>

std::string find_longest_nonrepeated(const std::string& str) {
	if (str.empty())
		return "";
		
	std::string longest;
	std::string curr;
	std::unordered_set<char> seen;
	
	for (char ch : str) {
		if (!seen.count(ch)) {
			curr.push_back(ch);
			seen.insert(ch);
		} else {
			if (curr.size() > longest.size()) {
				longest = curr;
			}
			curr.clear();
			seen.clear();
		}
	}
	
	if (curr.size() > longest.size())
		longest = curr;
	return longest;
}

int main() {
	std::cout << find_longest_nonrepeated("abcdffghijkabcxptoabccaldoajjz");
	std::cout << std::endl;
	return 0;
}

- Diego Giagio November 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution: -- Java version.

String str = "abcabaabccfdsaewer";
public static int maxNoRep(String str){
		int max = 0;
		if(str == null || str.length() == 0)
			return max;
		char current;
		String sub = "";
		for(int i = 0 ; i < str.length(); i++ ){
			current = str.charAt(i);
			if (sub.indexOf(current) != -1 ){
				int t = str.substring(0, i).lastIndexOf(current);
				sub = str.substring(t+1, i);
			}
			sub += current; 
			if( sub.length() > max)
				max = sub.length();
		}
		return max;
	}

- Doug December 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Construct a suffix tree.
Find the longest path in the suffix tree that doesn't have any overlap in characters.

For example ababc

Null
/ | \
c b ab
/ \ / \
abc c abc c
we can see that the last path yields abc our req soln.
There are good O(n) ways to construct suffix tree.

- Pras January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive approach

def maximum_subsequence_unique_character(string):
    char_map = {}
    maximum = 0
    for i in xrange(len(string)):
        if string[i] not in char_map:
            char_map[string[i]] = i
            maximum+=1
        else:
            maximum = max(maximum, maximum_subsequence_unique_character(string[char_map[string[i]]+1:]))
            break
    return maximum


print maximum_subsequence_unique_character("asdfabb12345hh123456789hh")

- ambu.sreedharan January 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;

public class SubStringWithNoDupChars {

	public static void main(String[] args) {
		String s = "sdgauravagarwaleabcdecafsg";
		int globallen = 0;                               //Global Max Length
		int locallen = 0;                                //Local Max length
		int r = 0;                                       //Last duplicate character index
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		char[] ca = s.toCharArray();
		for (int i = 0; i < ca.length; i++) {
			if (!map.containsKey(ca[i]) || map.get(ca[i]) < r) {
				locallen++;
			} else {
				if (locallen > globallen)  globallen = locallen;
				locallen = i - map.get(ca[i]);
				r = map.get(ca[i]);
			}
			map.put(ca[i], i);
		}
		System.out.println(globallen);
	}

}

- gauravonics January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		String s = "abcceddefaqqabcddddeeabcdefghipp";
		
		HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
		
		String maxSubstring = "";
		int maxSubstringLength = 0;
		int i = 0;
		for (int j = 0; j < s.length(); j++){
					
			// if the character does not exist then store the character as well as it's position
			if (hashMap.get(s.charAt(j)) == null) {
				hashMap.put(s.charAt(j), j);
			} else {
				
				// have i point a the new starting point
				i = hashMap.get(s.charAt(j)) + 1;
				
				// remove the hashed value
				hashMap.clear();
			}
			
			if (maxSubstringLength < getSize(i,j)) {
				maxSubstringLength = getSize(i,j);
				maxSubstring = s.substring(i, j+1); // inclusive 
			}
		}
		
		System.out.println(maxSubstring);
	}
	
	private static int getSize(int i, int j)
	{
		return Math.abs(i-j);
	}

- na123092 February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with O(n) complexity and without Hash Map.
This solution assumes that the string is comprised of only 'a-z' in lower case only. (But the solution can be extended for supporting other literals as well)
Hope this helps.

public String longestSubString(String str) {
		
		String longestSubStr = "";
		String longestSoFar = "";

		int[] arr = new int[26];
		for(int i=0;i<26; i++)
			arr[i]=-1;
		
		for(int i=0;i<str.length();i++) {
			char charac = str.charAt(i);
			int loc = charac -'a';
			if(arr[loc]==-1) {
				longestSoFar += charac;
				arr[loc] = i;
			}
			else if(longestSoFar.length()<(i-arr[loc])){
				longestSoFar += charac;
				arr[loc] = i;
			} 
			else {
				if(longestSoFar.length()>longestSubStr.length()) {
					longestSubStr = longestSoFar;
				}
				longestSoFar = str.substring(arr[loc]+1,i+1);
				arr[loc] = i;
			}
		}
		return longestSubStr;
	}

- akashgupta.edu April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with simple PHP

<?php

$str = 'abcdenmrstauvw';
$char_arr = array();
$tmp_str = $max_str = '';

for( $i=0; $i < strlen($str); $i++ ){
	
	if( isset( $char_arr[$str[$i]] ) ) {
		
		if( strlen($max_str) < strlen($tmp_str) ){
		
			$max_str = $tmp_str;
		}
		unset($char_arr);
		$tmp_str = '';		
	}

	$char_arr[$str[$i]] = $str[$i];
	$tmp_str .= $str[$i]; 	
	
}

if( strlen($max_str) < strlen($tmp_str) ){
		
	$max_str = $tmp_str;
}

echo $max_str;

- here.your.balaji April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int MaxSubString(string str)
        {
            int max = 0;
            int count = 0;
            int current = 0;
            Dictionary<char, int> result = new Dictionary<char, int>();
            while (current!=str.Length)
            {
                if (result.ContainsKey(str[current]))
                {
                    if (count > max)
                    {
                        max = count;
                    }
                    count = 0;
                    result.Clear();
                    str = str.Substring(current+1);
                    current = 0;
                }
                else
                {
                    result.Add(str[current], 1);
                    count++;
                    current++;
                }
            }
            if (count > max) max = count;
            return max;

}

- Tu April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
String source = "abacaimbuaposwggytelcbpenvyr";
PriorityQueue<String> longestQueue = new PriorityQueue<String>(5, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.length()-o1.length();
}
});

String sb = new String();
for (int i=0; i<source.length(); i++) {
char ch = source.charAt(i);
int positionOfChar = sb.indexOf(String.valueOf(ch));
if (positionOfChar<0) {
sb = sb + ch;
} else {
longestQueue.add(sb);
sb = sb.substring(positionOfChar+1)+ch;
}
}
System.out.println(longestQueue.poll());
}

- Eugene June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		String source = "abacaimbuaposwggytelcbpenvyr";
		PriorityQueue<String> longestQueue = new PriorityQueue<String>(5, new Comparator<String>() {
			public int compare(String o1, String o2) {
				return o2.length()-o1.length();
			}
		});
		
		String sb = new String();
		for (int i=0; i<source.length(); i++) {
			char ch = source.charAt(i);
			int positionOfChar = sb.indexOf(String.valueOf(ch));
			if (positionOfChar<0) {
				sb = sb + ch;
			} else {
				longestQueue.add(sb);
				sb = sb.substring(positionOfChar+1)+ch;
			}
		}
		System.out.println(longestQueue.poll());
	}

- Eugene June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
int t;
scanf("%d",&t);
while(t--){
char c[100001],ar[100001];int l,i,j,pos=-1,cnt=1,cur=1,max=1,x;
scanf("%s",c);fflush(stdin);
ar[0]=c[0];
l=strlen(c);
for(i=1;i<l;i++)
{
x=0;
for(j=pos+1;j<cnt;j++)
{
if(c[i]!=ar[j])
x++;
else if(c[i]==ar[j])
pos=j;
}
if(x==cnt)
{
ar[cnt++]=c[i];
cur=cnt;
}
else
{
ar[cnt++]=c[i];
if(cur<cnt-(pos+1))
{
cur=cnt-(pos+1);
}
}
if(max<cur)
{
max=cur;
}
}
printf("%d\n",max);
}
}

- rohit November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
int t;
scanf("%d",&t);
while(t--){
char c[100001],ar[100001];int l,i,j,pos=-1,cnt=1,cur=1,max=1,x;
scanf("%s",c);fflush(stdin);
ar[0]=c[0];
l=strlen(c);
for(i=1;i<l;i++)
{
x=0;
for(j=pos+1;j<cnt;j++)
{
if(c[i]!=ar[j])
x++;
else if(c[i]==ar[j])
pos=j;
}
if(x==cnt)
{
ar[cnt++]=c[i];
cur=cnt;
}
else
{
ar[cnt++]=c[i];
if(cur<cnt-(pos+1))
{
cur=cnt-(pos+1);
}
}
if(max<cur)
{
max=cur;
}
}
printf("%d\n",max);
}
}

- rohit November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String maxUniqueSubstring(String s){		
		int strlen = s.length();
		StringBuilder sb = new StringBuilder(strlen); // Use StringBuilder to save memory.
		String previousMax = ""; // The previous Max substring encountered
		String max = ""; // The current max substring
		boolean updateFlag = false; // Should max be updated from the StringBuilder
		Map<Character,Integer> fMap = new HashMap<Character,Integer>();
		
		for(int i=0;i<strlen;i++){
			Character nextChar = s.charAt(i);
			if(fMap.containsKey(nextChar)){ //character already present in current max
				// check whether to update max
				if(updateFlag){
					max = sb.toString();
					updateFlag=false;
				}
				sb = new StringBuilder(); // reset the StringBuilder
				sb.append(nextChar); 
				fMap.clear(); 
				fMap.put(nextChar,1); 
				// update previousMax if current max is longer
				if(max.length()>previousMax.length()){
				previousMax = max;
				}
			}else{
				// keep adding character to the builder
				sb = sb.append(nextChar);
				fMap.put(nextChar,1);
				if(max.length() < sb.length() && updateFlag==false){
					updateFlag=true; // Set the flag to update max when a duplicate occurs
				}
			}
		}
		// choose the maximum between previousMax and max
		if(previousMax.length()>max.length()){
			max = previousMax;
		}
		return max;
	}

- algorithmor May 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void function(string str, int& start, int& end)
{
    int hash[26] = {-1};
    for(int i=0;i<25;i++)
        hash[i] = -1;
    int left = 0, right = 0;
    hash[str[0]-97] = 0;
    for(int i=1;i<str.length();i++)
    {
        if(hash[str[i]-97] != -1 && hash[str[i]-97] >= left)
        {
            left = hash[str[i]-97]+1;
            right = i;
        }
        else
            right++;
        hash[str[i]-97] = i;
        if(right-left+1 >= end-start+1)
        {
            start = left;
            end = right;
        }
    }
}

- skum July 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String maxUniqueSubstring(String text) {
        Map<Character, Integer> m = new HashMap<Character, Integer>();
        int N = text.length();
        int maxStart = 0, maxLength = 0;

        for (int l = 0, r = 0; r <= N; r++) {
            if (r == N || m.getOrDefault(text.charAt(r), -1) >= l) {
                if (r - l > maxLength) {
                    maxLength = r - l;
                    maxStart = l;
                }

                if (r < N) {
                    l = m.get(text.charAt(r)) + 1;
                }
            }
            if(r < N) {
                m.put(text.charAt(r), r);
            }
        }

        return text.substring(maxStart, maxStart + maxLength);
    }

- eloi August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
    public static String maxUniqueSubstring(String text) {
        Map<Character, Integer> m = new HashMap<Character, Integer>();
        int N = text.length();
        int maxStart = 0, maxLength = 0;

        for (int l = 0, r = 0; r <= N; r++) {
            if (r == N || m.getOrDefault(text.charAt(r), -1) >= l) {
                if (r - l > maxLength) {
                    maxLength = r - l;
                    maxStart = l;
                }

                if (r < N) {
                    l = m.get(text.charAt(r)) + 1;
                }
            }
            if(r < N) {
                m.put(text.charAt(r), r);
            }
        }

        return text.substring(maxStart, maxStart + maxLength);
    }

- eloi August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why not just create a set out of the string to remove the repeated characters and return the length of that set? Am I missing sth here?! It will be O(n) clean and easy

- SJ February 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is O(n) runtime

public static int maxSizeUniqueCharSubstring(String s) {

        Map<Character, Integer> map = new HashMap<>();
        int lindex = 0;
        int rindex = 0;
        int max = 0;

        while (lindex < s.length()) {

            while ((lindex >= rindex || map.size() == rindex - lindex) && rindex < s.length()) {
                char c = s.charAt(rindex);
                rindex++;
                int size= rindex - lindex;
                Object o = map.get(c);
                if (o == null) {
                    map.put(c, 1);
                } else {
                    Integer i = (Integer) o;
                    i++;
                    map.put(c, i);
                }

                if ( size > max &&  map.size() == size) {
                    max = size;
                }
         
                
            }

            lindex++;

            char c = s.charAt(lindex - 1);
            Object o = map.get(c);
            if (o != null) {
                Integer i = (Integer) o;
                i--;
                if (i == 0) {
                    map.remove(c);
                } else {
                    map.put(c, i);
                }
            }

        }

        return max;
    }

- Steven November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution for lowercase only. The complexity is O(n) time and space.

def solve(string):
    ls = len(string)
    tr = lambda x: ord(x) - 97 
    lstring = map(tr, list(string))
    seqs = [[0 for _ in xrange(ls)] for _2 in xrange(26)]
    seqs[lstring[0]][0] = 1

    for i, c in enumerate(lstring[1:], 1):
        for letter in xrange(26):
            if letter == c:
                seqs[letter][i] = seqs[letter][i - 1] + 1
            else:
                seqs[letter][i] = seqs[letter][i - 1]

    best = 1
    for letter in xrange(26):
        c = seqs[letter]
        pv, pi = 0, -1
        cands = []
        for i, el in enumerate(c):
            if el != pv:
                cands.append((pi, i))
                pi, pv = i, el
        cands.append((pi, ls))

        for cand in cands:
            if cand[1] - cand[0] <= best:
                continue
            ok = True
            l, h = cand[0] + 1, cand[1] - 1
            for oletter in xrange(26):
                if oletter == letter:
                    continue
                o = seqs[oletter]
                if l != 0 and o[h] - o[l - 1] > 1 or o[h] > 1:
                    ok = False
                    break
            if ok:
                best = cand[1] - cand[0]

    return best
           

if __name__ == "__main__":
    from sys import argv
    print solve(argv[1])

- jakab922 February 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Modify Kadane's algo to keep track of unique chars instead of sums. Have a max_so_far variable with the longest substring found and the variables which hold the indexes. Have another variable max_current and another 2 variables for indexes. Iterate over the array and update the max_current variable. Once you hit a duplicate if max_current is greater than max_so_far update max_so_far and the indexes and clear max_current.
Time complexity O(N) space complexity O(1).

- pittbull November 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interesting if possible. Pseudocode for bigO (1) space alg?

- urik on bb November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

how you know a character is duplicate with o(1) space complexity? You actually need a hash to store the last seen index for each character and that's O(n) space. Alternatively you could traverse the current substring but that would make the time complexity O(n^2). It's a trade off you can not avoid.

- uruk hai November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cool name uruk !

- S O U N D W A V E November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Uruk is right, space complexity is actually O(n)

- Murali Mohan November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agree. with uruk

- Stupid Developer November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ajeet do it below O(n) but his code separating all over. But it is good codes.

-Guest DS

- algos November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Here is my approach:
It as time complexity O(N) and space complexity O(size of window)

I am using a hash table to track characters in current window. 
If an duplicate occurs than I just move start position to previous index of this character(Hash table has previous index). And clear hash table, for next window.
Check if previous window size is smaller than (start - current pointer ), than just replace window with (start - current pointer ).

Here is implementation in java:
	public static int find(String source){
		int window = 0;
		int start = 0;
		int i =0;
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		while( i < source.length()){
			if(map.containsKey(source.charAt(i))){	
				int currentWindow = i-start;
				if(window < currentWindow){
					window = currentWindow;
				}
				start = i;
				map.clear();
			}
			if(i+1 == source.length()){
				int currentWindow = i-start +1;
				if(window < currentWindow){
					window = currentWindow;
				}
				return window;
			}
			map.put(source.charAt(i), i);
			i++;
		}	
		return 0;
	}

- Ajeet November 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Visualization: Iteration 0:
------------
|
"AABC"
window = 0;
sart =0;
i = 0

Iteration 1:
-------------
|
"AABC"
window = 1; (1 -0)
start = 1; duplicate occurs so move it
i = 1

Iteration 2:
-------------
|
"AABC"
window = 1;
start = 1;
i = 2

Iteration 3:
-------------
|
"AABC"
window = 3; (i - start) +1
start = 1;
i = 3 // we are reaching end of string so check for last

- Ajeet November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ajeet -> Why are you clearing the whole map on finding a duplicate character ?
Eg : IF the string is "abac" . Then the expected o/p is "3" (string "bac").

- Anonymous November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your prog does not work for this input :

ABCDEBFRT (ans shud be 7 it gives 5)

- Alok November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Your prog wont work for this case :

ABCDEBFTR

Solutions : Inside if loop when key is matched, start=i should be replaced with -

start = map.get(source.charAt(i))+1;

- Alok Kumar November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Alok. Yes it should be map.get(source.charAt(i))+1.

- Ajeet November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry ... it should be .. start = map.get(source.charAt(i)) + 1;

- Ajeet November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous
Yes it will work with out map.clear().
I was using this statement to reduce space allocation.

- Ajeet November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

After modification ..

public static int find(String source){
		int window = 0;
		int start = 0;
		int i =0;
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		while( i < source.length()){
			if(map.containsKey(source.charAt(i))){	
				int currentWindow = i-start;
				if(window < currentWindow){
					window = currentWindow;
				}
				start = map.get(source.charAt(i)) + 1;
				//map.clear();
			}
			if(i+1 == source.length()){
				int currentWindow = i-start +1;
				if(window < currentWindow){
					window = currentWindow;
				}
				return window;
			}
			map.put(source.charAt(i), i);
			i++;
		}	
		return 0;
	}

- Ajeet November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Ajeet d u m p a s s ruin the whole cracking careercup.

MORON.

- *anon* November 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ajeet
what does O(size of window) mean? how size of the window is related to N? right, it's max N, means space complexity is O(N), and your attempt to decrease memory footprint looks funny taking into account it doesn't improve anything O-wise.

- jopa.singh November 14, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More