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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

Java Program using HashSet

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        HashSet<Character> window = new HashSet<>();
        
        int left = 0,right = 0;
        
        int maxLen = 0;
        
        while(right < s.length()){
        
            while(window.contains(s.charAt(right)))
                window.remove(s.charAt(left++));
           
            window.add(s.charAt(right++));
            
            maxLen = Math.max(maxLen,right-left);
        }
        
        return maxLen;
    }
}

Java Program using HashMap

   public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }

Time Complexity: O(n)

Space Complexity: O(n)