My accepted O(n) Java solution


  • 9
    S

    As soon as we see a duplicated character, calculate the length of the substring and start the search one character away from the previous start.

    class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length();
            if (n == 0) return 0;
            
            int start = 0;
            int max = 0;
            Map<Character, Integer> lastSeens = new HashMap<Character, Integer>();
            for (int i = 0; i < n; i++) {
                Integer lastSeen = lastSeens.get(s.charAt(i));
                
                if (lastSeen != null)  {
                    if (lastSeen >= start) {
                        max = Math.max(max, i - start);
                        start = lastSeen + 1;
                    }
                }
                lastSeens.put(s.charAt(i), i);
            }
            max = Math.max(max, n - start);
            
            return max;
        }
    }

  • 0
    L

    My first attempt with a O(n^2) algorithm failed the time limit, without much surprise. Then I figured out this is actually a DP problem. My solution shares the same idea as the above solution.

    The problem can be solved in the following steps:
    e.g. ABCA

    1). Starting from “A”, the maximum non-repetitive substring it can reach is “ABC”. We could say the optimal value for the first “A” is 3.

    2). Then for the next element “B”, one could start to build the substring based on previous results from “A”. Namely, we could first remove “A” from the previous optimal substring, and start from the next element after the optimal substring “BC” to find another potentially long substring.

    In general, the about DP algorithm has a O(N) complexity.

    Here is the code. Not so much elegant though…

    public int lengthOfLongestSubstring(String s) {
    	if(s == null || s.length() == 0){
    		return 0;
    	}
    	int end = s.length();
    	int max_size = Integer.MIN_VALUE;
    	int pre_max_value = 0;
    	
    	HashSet<String> dict = new HashSet<String>();
    	dict.add(String.valueOf(s.charAt(0)));
    	int count = 1;
    	
    	// Initialize the dictionary 
    	for(int j=1; j<end; j++){
    		String k = String.valueOf(s.charAt(j));
    		
    		if(dict.contains(k)){
    			break;
    		}else{
    			dict.add(k);
    			count ++;
    		}
    	}
    	pre_max_value = count;
    	max_size = pre_max_value;
    	
    	if(max_size == end){
    		// early exit;
    		return max_size;
    	}
    	
    	// Go through the rest of the elements one by one. 
    	for(int i=1; i < end; i++){
    		String preK = String.valueOf(s.charAt(i-1));
    		dict.remove(preK);
    		
    		count = pre_max_value - 1;
    		for(int j=i+count; j<end; j++){
    			String newK = String.valueOf(s.charAt(j));
        		
    			if(dict.contains(newK)){
        			break;
        		}else{
        			dict.add(newK);
        			count ++;
        		}	
    		}
    		
    		// prepare for the next one 
    		pre_max_value = count;
    		
    		if(count > max_size){
    			max_size = count;
    		}
    		
    		// early return;
    		if(pre_max_value + i == end){
    			break;
    		}	
    	}
    	
    	return max_size;
    }
    

  • 0
    Y
    public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int array[]=new int[128];
        Arrays.fill(array,-1);
        int len=0;
        int start=-1;
        for(int i=0;i<s.length();i++)
        {
                start=start>=array[s.charAt(i)]?start:array[s.charAt(i)];
                len=(i-start)>len?(i-start):len;
                array[s.charAt(i)]=i;
        }
        return len;
    }
    

  • 0
    A
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.