# 3. Longest Substring Without Repeating Characters

Leetcode

#### <https://leetcode.com/problems/longest-substring-without-repeating-characters/description/>

### 題目

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

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "abcabcbb"
</strong><strong>Output: 3
</strong><strong>Explanation: The answer is "abc", with the length of 3.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "bbbbb"
</strong><strong>Output: 1
</strong><strong>Explanation: The answer is "b", with the length of 1.
</strong></code></pre>

**Example 3:**

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - Sliding window**

題目需要求的是最長的子字串，並且子字串中的字母都不重複，所以思考方向很簡單，由左往右遍歷當新添加進來的字母並不在子字串中的話就代表可以繼續，但如果有遇到重複的字母時，就需要將子字串中之前遇到的同個字母從左邊開始一直移除

範例：`"abcabcbb"`

遍歷到第三個元素(c)時：

子字串會是 `"abc"`

接著遍歷到第四個元素(a)時：

發現已經跟子字串中的第一個元素重複了，所以需要將第一個元素刪除，因此此時的子字串會變為 `"bca"`

遍歷到第五個元素(b)時：

發現也跟子字串中的第一個元素重複了，刪除第一個元素，此時子字串為 `"cab"`

......

......

這樣依序遍歷下去，每一輪中也順便統計最長的子字串長度後，就可以求得解答了

```javascript
var lengthOfLongestSubstring = function(s) {
    const arr = [];
    let max = 0;

    for (let i=0; i<s.length; i++) {
        const value = s[i];
        while(arr.includes(value)) {
            arr.shift();
        }
        arr.push(value);
        max = Math.max(max, arr.length);
    }

    return max;
};
```

Runtime: 80 ms Beats 67.85% of users with JavaScript

Memory: 53.52 MB Beats 47.06% of users with JavaScript

### 參考資料

{% embed url="<https://hackmd.io/@SupportCoding/Sliding_Window>" %}

### 延伸題目

[424. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)
