CareerCup

input: input string
1. keep a set with all characters in a window [s, e]
2. start with s = 0
3. increment e as long as input[e] not already in set
[s, e) is now a candiate, maximize it
now increment s until input[s] = input[e] and remove each input[s] from the set
go to 3

runs in O(n) with O(n) space for result

def find_longest_substring_wo_repeating_char(input):
    n = len(input)
    s = 0
    e = 0
    chars = set()
    result = ''
    while e < n:
        while e < n and input[e] not in chars:
            chars.add(input[e])
            e += 1        
        
        if len(result) < e - s:
            result = input[s:e]
        
        if e < n:
            while input[s] != input[e]:
                chars.remove(input[s])
                s += 1
            chars.remove(input[s])        
            s += 1
    return result

print(find_longest_substring_wo_repeating_char('aabbcde'))
print(find_longest_substring_wo_repeating_char('a'))
print(find_longest_substring_wo_repeating_char('ab'))
print(find_longest_substring_wo_repeating_char('abc'))
print(find_longest_substring_wo_repeating_char('abccc'))
print(find_longest_substring_wo_repeating_char('abcccdefg'))
# output:
# bcde
# a
# ab
# abc
# abc
# cdefg

import java.util.ArrayList;
import java.util.HashSet;

public class UniqueSubString {

	public static void main(String[] args){
		System.out.println(findLongestSubString("aabbcde"));
		System.out.println(findLongestSubString("abccc"));
		System.out.println(findLongestSubString("abcccdefg"));		
	}

	public static String findLongestSubString(String str){
		HashSet<Character> set = new  HashSet<>();
		ArrayList<String> list = new ArrayList<>();
		int maxSizeIndex =0;
		int maxSize = 0;
		for(int i=0;i<str.length();i++){
			if(set.contains(str.charAt(i)) || i==str.length()-1) {
				
				
				String substr = "";				
				for(Character char2:set){
					substr+=char2;
				}
				if(i==str.length()-1) substr+=str.charAt(i);
				list.add(substr);
				if(maxSize < substr.length()) {
					maxSize = set.size();
					maxSizeIndex = list.size()-1;
				}					
				set.clear();
			}
			set.add(str.charAt(i));
		}
		return list.isEmpty()?null:list.get(maxSizeIndex);	
	}

}

I dont see this code giving the right output for the following string:

abcdcefghi

This doesnt seem to be working for the following string:
abcdcefghi

static void printLongestSubstringNoDuplicateChars(String s){
		
		int startIndex = 0, endIndex = 0;
		StringBuilder previousString = new StringBuilder();
		
		while(endIndex < s.length()){
			
			Set<Character> set = new HashSet<>();
			StringBuilder currentString = new StringBuilder();
			
			while(endIndex < s.length() && set.add(s.charAt(endIndex))){
				currentString.append(s.charAt(endIndex));
				endIndex++;
			}
			
			startIndex = endIndex;
			endIndex = startIndex;
			
			if(currentString.length() > previousString.length()){
				previousString = currentString;
			}
		}
		
		System.out.println(previousString.toString());
		
	}

static void printLongestSubstringNoDuplicateChars(String s){
		
		int startIndex = 0, endIndex = 0;
		StringBuilder previousString = new StringBuilder();
		
		while(endIndex < s.length()){
			
			Set<Character> set = new HashSet<>();
			StringBuilder currentString = new StringBuilder();
			
			while(endIndex < s.length() && set.add(s.charAt(endIndex))){
				currentString.append(s.charAt(endIndex));
				endIndex++;
			}
			
			startIndex = endIndex;
			endIndex = startIndex;
			
			if(currentString.length() > previousString.length()){
				previousString = currentString;
			}
		}
		
		System.out.println(previousString.toString());
		
	}

import java.util.ArrayList;

public class LongestSubstringWithoutRepeatingCharacter {

	public static void main(String[] args) {
		
		String str = "abhdhknxkjankzj";
		String result = "";
		int index = 0;
		ArrayList<Character> list = new ArrayList<Character>();
		
		for(int i=0; index<str.length();){
			
			list.add(str.charAt(i));
			
			for(int j=i+1;j<str.length(); j++)
				
				if(list.contains(str.charAt(j))){
					
					index += list.indexOf(str.charAt(j));
					
					String subStr = (String) str.subSequence(i, j);
					
					if(subStr.length() > result.length())
						result = subStr;	
					
					break;
				}
				else
					list.add(str.charAt(j));
			
			list.clear();
			i = ++index;
		}
		
		System.out.println("Result = " + result);

	}

}