Simple Java Solution O(n)


  • 0
    D

    public class Solution
    {

    // In this problem I have used kind of a sliding window approach

    public int lengthOfLongestSubstring(String s)
    {

        int i=0,j=0,max=0,index=0;
        
        //Here i stores the current element
        //j stores the start of the window
        //max stores the max length
        // we'll see about index below
        
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        for(;i<s.length();++i)
        {
            
            //If the element is seen for the first time we put it in the map
            //The max length is from j to i which is calculated as (i-j+1)
            if(i==0 || !map.containsKey(s.charAt(i)))
            {
                map.put(s.charAt(i),i);
                max = Math.max(max,i-j+1);
            }
            else
            {
                index=map.get(s.charAt(i));  //Here index gets the previous occurence position
                
                //If index is not in our window we don't need to care about it so we remove it from the map
                if(index<j)
                    map.remove(s.charAt(i));
                //If it lies the window then our window has reached it's end and we create a new window from index+1 
                else
                    j=index+1;
                //If our the start of our new window is from the current element the we may as well discard the map
                //and create a new map
                //This is for the test case "abba"
                if(i==j)
                    map.clear();
                //Here we store the new occurence and calculate the new length
                map.put(s.charAt(i),i);
                max = Math.max(max,i-j+1);
            }
        }
        return max;
    }
    

    }


Log in to reply
 

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