An easy-to-understand, linear time solution with explanation


  • 0
    M
    public class Solution {
        public static int lengthOfLongestSubstring(String s) {
                    //an array initialized with 0 used for counting characters
    		int[] count = new int[256];           
    		int maxLength = 0, currentLength = 0, startIndex = 0, endIndex = 0;
    		for (int i = 0; i < s.length(); i++){
                            //update the counting array
    			int index = s.charAt(i);
    			count[index]++;                  
    			if (count[index] == 1){ 
                                    //there is no duplicate adding the last character        
    				endIndex = i;
    				currentLength = endIndex - startIndex + 1;
    				maxLength = Math.max(currentLength, maxLength);
    			} else {   
                                    //there is a duplicate adding the last character  
                                    //increase the start index until the condition is satisfied                       
    				while(count[index] > 1)
    					count[s.charAt(startIndex)]--;
    					startIndex++;
    				}
    			}
    		}
    		return maxLength;
    	}
    }
    

Log in to reply
 

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