# 3. Longest Substring Without Repeating Characters

[ **3. Longest Substring Without Repeating Characters**](https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)

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

**Examples:**

Given `"abcabcbb"`, the answer is `"abc"`, which the length is 3.

Given `"bbbbb"`, the answer is `"b"`, with the length of 1.

Given `"pwwkew"`, 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.<br>

***My Solutions:***

用hashset确保set里没有重复字母，l 是sliding window 的start，r 是移动的end

```java
public int lengthOfLongestSubstring(String s) {
    int len = s.length(), l = 0, r = 0, ans = 0;
    Set<Character> set = new HashSet<>();
    while (l < len && r < len) {
        if (!set.contains(s.charAt(r))) { // 如果window末尾的字母没有出现过
            set.add(s.charAt(r++)); // 先移动r，增加window的长度
            ans = Math.max(ans, r - l); // 计算长度最大值
        } else { // 如果当前字母已经出现过，需要移动窗口
            set.remove(s.charAt(l++)); // 把当前在l位置的字母去除，并且l++
        }
    }
    return ans;
}
```

可以用hashmap进一步优化，map里记录每个字母出现的最后一个index。窗口不需要每次只移动一个位置，直接把窗口移动到最后的位置。

* Time complexity: O(n)
* Space complexity: O(n)

```
public int lengthOfLongestSubstring(String s) {
    int len = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>(); 
    for (int l = 0, r = 0; r < len; r++) {
        char c = s.charAt(r);
        if (map.containsKey(c)) {
            // l needs to be moved to the position after the last occurring position of c
            // 或者现在l所在的位置。这样保证了window总是向右移动
            l = Math.max(map.get(c) + 1, l);
        }
        ans = Math.max(ans, r - l + 1);
        map.put(c, r); // map里记录的是c最后出现的index，此时的index=r
    }
    return ans;     
}
```