Example: Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Solution

We process character by character

• We try to add the current char to the set, if it is not present, we increase current len by 1
• If we find a repeated character
  • we advance the left pointer until after the previous instance of that character and compute len again.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> chars = new HashSet<>();
        int longest = 0;
        int left = 0;
        
        for (int right = 0; right < s.length(); right++) {   
            // it's ok to do this, String uses an array internally so there is only an extra range check compared
            // to using a char array directly
            char currentChar = s.charAt(right);
            
            if (!chars.add (currentChar)) {
                while (s.charAt (left) != currentChar) {
                    chars.remove (s.charAt(left));
                    left++;
                }
                // we move the pointer to the first instance of the repeated char so we can
                // create the new sequence
                left++;
            }
            
            // array starts from 0 so need to add 1
            longest = Math.max(longest, right - left + 1);
        }
        return longest;
    }
}