# LeetCode 3. Longest Substring Without Repeating Characters (Java)
###### tags: `leetcode` `Java` `substring`

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

>找出字串s中沒有重複最長的子字串(substring)的長度

## Example

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 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.

## Idea
- 使用**移動窗格**方式去找出最大子字串
- 每個迴圈窗格`window`都往右移一格，並且判斷窗格內是否有與新加入的字元重複，如有重複將左邊指標`left`往右刪除字元直到窗格內未有重複字元為止
- ==**HashSet**不會加入重複字元或字串==
- `max_len`會在移動窗格最後判斷目前合法的窗格長度是否大於原本的值

## Code
這樣的寫法會使時間複雜度為 $O(n)$，會遍歷整個字串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null) return 0;
        
        HashSet<Character> window = new HashSet<Character>();
        int max_len = 0;
        int left = 0;
        int len = 0;
        char[] ss = s.toCharArray();
        for (int i = 0;i < s.length();i++){
            while(window.contains(ss[i])){ //判斷是否有重複字元
                window.remove(ss[left]);
                left++; //指標因刪除往右一格
                len--;
            }
            window.add(ss[i]);
            len++;
            if(max_len < len)
                max_len = len;
        }
        return max_len;
    }
}