# 3. Longest Substring Without Repeating Characters

###### tags: `leetcode`,`sliding window`,`medium`

>ref: https://leetcode.com/problems/longest-substring-without-repeating-characters/
>
Given a string s, find the length of the longest substring without repeating characters.

>Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

>Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

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


>1. timeCom:O(N) no spatail
>2. count計算start與end的差異,map 記憶該char所在位置, 計算時end需+1才會計算到包含當下char之長度, 當遇到曾出現的char時,須更新start位置,由於重複 且計算時會包含end char 故start當使用map位置時需要加一(排除先前出現的char位置), 發現重複char後需要更新在map中之位置

    public int lengthOfLongestSubstring(String s) {
        
        Map<Character,Integer> map = new HashMap<>();
        
        int start=0;
        int end=0;
        
        int count=0;
        int max=0;
        
        while(end<s.length()){

            if(map.containsKey(s.charAt(end))){
                start=Math.max(map.get(s.charAt(end))+1,start); // +1 for over the repeat char
            }
            map.put(s.charAt(end),end);
            
            end++;//contain end
            
            count=end-start;
            
            max=Math.max(count,max);
        }
        
        return max;
    }