Amazon Interview Question
SDE-2sTeam: Cyllas Experience
Country: India
Interview Type: In-Person
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;
}
}
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;
}
}
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;
}
This is not working for some example. There is a bug!
//For example
String str = "abcabaabccfdsaewer"; //Should return "cfdsaew", but returns "abaabccfds"
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();
}
}
@techpanja I think your code wont work on "abcba", it returns abcb which is wrong, answer should be "abc".
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;
}
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');
}
}
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, why you fill up the careercup posting by separating all over?
It is annoy people.
-Guest DS
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
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
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
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.
@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".
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;
}
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;
}
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);
}
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;
}
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);
}
}
#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;
}
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
I think you need to reset the flags array whenever the beginOffset is reset to i.
Take an example string of "BAABCdefghhijkl"
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;
}
// 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));
}
}
all these O(1) space, O(strlen) time solutions.... Wow!
Now waiting for O(1) time and space solutions to be posted :P
If the characters are a-z, then O(1) space algorithms exist.
############# Go away, troll. ###############
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.
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. 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 ##########################
No it is cache oblivious model of computation. Subbu is level 1 troll. Nothing compred to Anonymous.
@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 ######################
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. 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.
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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));
}
}
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));
}
}
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());
}
}
<?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);
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;
}
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;
}
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")
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);
}
}
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);
}
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;
}
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;
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;
}
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());
}
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());
}
#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);
}
}
#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);
}
}
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;
}
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;
}
}
}
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);
}
{
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);
}
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;
}
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])
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).
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.
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;
}
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 -> 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").
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;
@Anonymous
Yes it will work with out map.clear().
I was using this statement to reduce space allocation.
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;
}
- techpanja November 12, 2013