[Day5]3. Longest Substring Witho

Finally, I have the courage to choose one of MEDIUM level. Sometimes, I do question my IQ. This problem, takes me two more than one hour to finish!!

DESCRIPTION:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

ANALYSIS:
At first, I didn't think too much, so I used two loops... And, no doubt, Time Limit Exceeded!
Then, I refine to one loop and it takes as much time as the top solution. So, I didn't study the top solution.
The algorithm I use may be called 'DongTaiGuiHua'. Hha~. Maybe, I am not sure, last time I learn algorithm to solve ACM problem can date back to almost two yeas ago? That algorithm leave me the impression like 'start from zero and loop', 'include one more', 'compare and juge', 'update the -est', And when the loop finish, the result also come up!

SOLUTION:

public static int lengthOfLongestSubstringTLE(String s) {
    String longest="";
    for(int i=0;i<s.length();i++){
        String temp="";
        for(int j=i;j>=0;j--){
            if(!temp.contains(""+s.charAt(j))){
                temp=s.charAt(j)+temp;
            }else {
                break;
            }
        }
        if(temp.length()>=longest.length()){
            longest=temp;
        }
    }
    return longest.length();
}

public static int lengthOfLongestSubstring(String s) {
    String longest="";
    String last="";
    for(int i=0;i<s.length();i++){
        if(last.contains(""+s.charAt(i))==true){
            int l=last.indexOf(s.charAt(i));
            last=last.substring(l+1)+s.charAt(i);
        }else{
            last=last+s.charAt(i);
        }
        if(last.length()>=longest.length()){
            longest=last;
        }
    }
    return longest.length();
}

public int lengthOfLongestSubstringTop(String s) {
    if (s.length()==0) return 0;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int max=0;
    for (int i=0, j=0; i<s.length(); ++i){
        if (map.containsKey(s.charAt(i))){
            j = Math.max(j,map.get(s.charAt(i))+1);
        }
        map.put(s.charAt(i),i);
        max = Math.max(max,i-j+1);
    }
    return max;
}