My 9-line,O(n) , Java solution - Accepted(488 ms)


  • 0
    T

    runLength variable tracks the length of the longest non-repeating substring at any given index. We maintain a hashmap of already seen characters along with their index. If the current character is found in the map and it is within the range of runLength, then it is a repeated character with respect to current substring (tracked by runLength). So we update the map and runLength appropriately. Else, we increase the runLength.
    Also notice that maxLength can be updated only in the else case.

     public int lengthOfLongestSubstring(String s) {	 
    	        int runLength = 0, maxLength = 0;
    	        int strLen = s.length();
    	        HashMap<Integer,Integer> index = new HashMap<Integer, Integer>();
    	        for(int i = 0 ; i < strLen ; i++){
    	        	Integer p = index.get(s.codePointAt(i));
    	        	if(p != null && p >= i-runLength)
    	        		runLength = i - p;
    	        	else
    	        		maxLength = Math.max(maxLength, ++runLength);
    	        	index.put(s.codePointAt(i), i);	        		
    	        }
    	        return maxLength;
    	    }

Log in to reply
 

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