Java, using Hashset, O(n) time complexity, with explanation


  • 0
    D
    public class Solution {
        public int lengthOfLongestSubstring(String s) 
        {
            if (s == null || s.length() < 1) { return 0;}
            
            char[] str = s.toCharArray();
            // using set to deduplicate
            Set<Character> st = new HashSet<>();
            st.add(str[0]);
            
            int maxLength = 1;
            // point to substring's left end
            int i = 0;
            // point to substring's right end
            int j = 1;
            
            while (j < str.length)
            {
                // find duplicates
                if (st.contains(str[j]))
                {
                    // calculate current substring length and select max one
                    maxLength = Math.max(maxLength, j - i);
                    // move str[i] from set until arrives character that equals to str[j]
                    while (i < str.length && str[i] != str[j]) 
                    { 
                        st.remove(str[i]);
                        i++; 
                    }
                    // update pointers
                    i++;
                    j++;
                }
                else 
                { 
                    st.add(str[j]);
                    j++; 
                }
            }
            // final calculate
            maxLength = Math.max(maxLength, j - i);
            
            return maxLength;
        }
    }
    

Log in to reply
 

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