LeetCode: Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters



Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1

Solution 1: Use two pointers to track each maximal non-repeating window. Time requirement is O(n). 

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        //Map<Character,Integer> found = new HashMap<Character,Integer>();
        boolean[] flag= new boolean[256];
        
        char[] c = s.toCharArray();
        int i=0,j=0,res=0;
        while(i<c.length){
            if(flag[c[i]]==true){
                res=Math.max(i-j,res); 
                for(int k=j;k<i;k++){
                    if(c[k]==c[i]){
                        j=k+1;
                        break;
                    } 
                    flag[c[k]]=false;
                }
            }else
                flag[c[i]]=true;
            i++;
        }
        res=Math.max(c.length-j,res);
        return res;
    }
}

Solution 2:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        //Map<Character,Integer> found = new HashMap<Character,Integer>();
        char[] c = s.toCharArray();
        int j=0,res=0;
        for(int i=0;i<c.length;i++){
            for(int k=j;k<i;k++){
                if(c[k]==c[i]){
                    res=Math.max(i-j,res);
                    int temp=i;
                    while(i+1<c.length&&c[i]==c[i+1])
                        i++;
                    if(i>temp){
                        j=i;
                    }else{
                        j=k+1;
                    }
                    break;
                }
            }
        }
        res=Math.max(c.length-j,res);
        return res;
    }
}