http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/
Round3, Q1
Given a string, find the longest substring without repeating characters. For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA” and “DEFGAB”.
Instead of using a array for all 26 alphabets, I use hashmap to store the char which are already read.
/*
* http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/
* Round3, Q1
* Given a string, find the longest substring without repeating characters.
* For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA” and “DEFGAB”.
*/
import java.util.HashMap;
public class LengthOfLongestSubstringWithoutRepeating {
public static int findLongestSubstringWithoutRepeating(String s){
if(s==null){
return -1;
}
HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
int max_start = 0; //Record the position where the max substring starts
int max_len = 1; //Record the length of max substring
int curr_len = 1; //Record the length of current substring
hm.put(s.charAt(0), 0);
for(int i=1;i<s.length();i++){
if((hm.get(s.charAt(i))==null)||(i-curr_len>hm.get(s.charAt(i)))){
//Current char hasn’t been read, or position of previous char c is not in the range of current substring
curr_len++;
hm.put(s.charAt(i), i);
}
else{
if(curr_len>max_len){ //Find a new max length, update the max_len
max_len = curr_len;
max_start = i – curr_len;
}
curr_len = i – hm.get(s.charAt(i)); //Calculate the new length of current substring
hm.put(s.charAt(i), i);
}
}
// System.out.println(“max start:” + max_start);
// System.out.println(“max len:” + max_len);
return max_len;
}
public static void main(String[] args) {
//String str = “abcdefeczqposc”;
String str = “GEEKSFORGEEKS”;
int max_len = findLongestSubstringWithoutRepeating(str);
System.out.println(max_len);
}
}