Need feedback from readers : My accepted java solution using hash set and two pointers.


  • 0
    S

    It uses two pointers and a hash set. Slow pointers starts at 0 and fast pointer at 1. Hash set tracks the characters present between the slow and fast pointers.
    Fast pointer is incremented and the character at the fast pointer is added to the set until a repeating character is encountered. Substring length is computed at this stage.
    The slow pointer now moves one to the right and the character at the previous slow pointer position is removed from the hash set. The loop continues.

    Need feedback from readers : I want to know if the time complexity on this one is still O(n) - assuming O(1) for hash set.
    Notice that every time a repeating character is encountered, fast pointer is not incremented, which means for certain substrings the character at the same fast pointer position would be checked twice against the set.

    public int lengthOfLongestSubstring(String s) {
            if(s==null || s.length()==0)
            {
                return 0;
            }
            
            Set set = new HashSet();
            int sp=0, fp= 1, count =1;
            set.add(s.charAt(sp));
            
            while(sp<s.length() && fp<s.length())
            {
                if(set.contains(s.charAt(fp)))
                {
                    count = Math.max(count, fp - sp);
                    set.remove(s.charAt(sp));
                    sp++;
                }
                else
                {
                    set.add(s.charAt(fp));
                    fp++;
                    if(fp==s.length())
                    {
                        count = Math.max(count, fp-sp);
                    }
                }   
            }
            return count;
        }
    

Log in to reply
 

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