---
tags: leetcode, medium, sliding window
---
# LeetCode 3. Longest Substring Without Repeating Characters
<font color="#ef6c00">Medium</font>
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.
```
Example 4:
```
Input: s = ""
Output: 0
```
Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
#### 解決方法 1
暴力解法，我們依序把每個字元當作起點，從它開始往後遍歷每個字元直到出現重複的字元為止，記錄下最長的長度。為了檢查是否有重複的字元出現，我們使用 `Set` 儲存每個遍歷到字元。
###### Java Code
```java=
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() == 1) {
// 處理特殊狀況
return 1;
}
Set<Character> substring = new HashSet<>();
int longest = 0;
// 因為我們會往後遍歷所以終點為長度 - 2
for (int i = 0; i < s.length() - 1; i++) {
substring.add(s.charAt(i));
for (int j = i + 1; j < s.length(); j++) {
if (!substring.add(s.charAt(j))) {
break;
}
}
// substring 的長度即為本次遍歷在遇到重複字元前的長度
longest = Math.max(longest, substring.size());
// 清除內容以記錄下次遍歷的字元
substring.clear();
}
return longest;
}
}
```
時間複雜度：因為我們會從每個字元為起點遍歷一次，所以長度為 $N$，則我們進行 $(N - 1) + (N - 2)...+ 1 = N(N + 1) / 2 = (N^2 + N) \times 1/2$，所以時間複雜度為 $O(N^2)$
#### 解決方法 2 (LeetCode Solution)
使用 **Sliding Window Algorithm**。Sliding Window Algorithm 是建立一區間稱為 **windows**，比方區間起點是 index `i`，而終點是 index `j`，我們用 `[i, j)` 表示這個區間以 `i` 為起點，而 `j` 會待續移動。
同時我們用 1 個 `Set` 記錄下目前 `[i, j)` 中的字元，我們每次檢查 `j` 指向的字元是否存在於 `Set` 之中，如果沒有的話，我們就把該字元加進 `Set` 中，接著 `j` 再往右延展一位。等到 `j` 指向的字元存在 `Set` 中時表示有重複的字元，這時 `[i, j)` 的區間長度即為可能的最長不重複字元子字串的長度，我們再和目前記錄的最長長度 `maxLogest` 比較，如果新的長度比較長就取代掉 `maxLongest`。
因為我們只知道 `[i, j)` 中有重複的字元，但不曉得是哪一個，同時我們知道如果重複字元的 index 為 `k` 則 `[k, j)` 必小於 `[i, j)` 所以我們將 window 的起點右移 1 位再檢查一次是否有重複字元，直到沒有重複字元的 `[i, j)` window 才有可能有比原本 window 更長的子字串出現。
具體的步驟為把 windows 縮小變成 `[i + 1, j)`，同時把原本 `i` 指向的字元從 `Set` 中移除，然後再檢查 `j` 是否包含在新的 window 字串內，如果同樣包含就再縮小 windows `[i + 2, j)`，直到在 windows 字串內沒有重複的字元後再繼續之前的步驟。
###### Java Code
```java=
class Solution {
public int lengthOfLongestSubstring(String s) {
// window 起點
int i = 0;
// window 終點
int j = 0;
// 記錄最長不重複字元子字串長度
int maxLongest = 0;
// 記錄 window 內出現的字元用來比對是否有重複字元
Set<Character> substring = new HashSet<>();
while (j < s.length()) {
// Java 的 Set.add 如果回傳 true 表示沒有重複元素
if (substring.add(s.charAt(j))) {
// 因為是是 0 based, 所以計算長度要 + 1
maxLongest = Math.max(maxLongest, j - i + 1);
j++;
} else {
// 縮小 window 長度, 同時移除原本 i 指向的字元
substring.remove(s.charAt(i++)));
}
}
return maxLongest;
}
}
```
- 時間複雜度：因為每個元素都會被 `i`、`j` 存取到，所以如果有 $N$ 個元素則為 $O(2N)$ 也就是 $O(N)$。
- 空間複雜度：我們需要 `Set` 記錄 window 內的字元，所以 `Set` 的長度取決於 window 的長度。如果字串完全沒有重複字元，則 window 長度即為輸入字串的長度 $N$，所以空間複雜度為 $O(N)$，如果有重複字元出現則 window 的長度即為不重複字元子字串長度 $M$，所以空間複雜度為 $O(min(M, N))$
#### 解決方法 3 (LeetCode Solution)
如解決方法 2 提到的，當出現重複字元時，因為我們不知道重複字元的 index 為何，所以我們必須慢慢縮減 window 的長度來找到新的起始位置，所以每個字元可能都需要存取 2 次，如果我們記錄下 window 中每個字元的 index，就可以直接從重複字元的 index 開始，這樣每個字元的存取數就變成 1 次。
具體的方法是改用 `Map` 記錄每個字元和它所在的 index，如果出現重複的字元就可以直接取得新的起始位置。
###### Java Code (根據概念自寫)
```java=
class Solution {
public int lengthOfLongestSubstring(String s) {
// 記錄 window 起始 index
int i = 0;
// 記錄 window 終點 index
int j = 0;
// 記錄目前最長不重複字元子字串
int maxLongest = 0;
// 記錄 window 中每個字元和它所在的 index
Map<Character, Integer> substring = new HashMap<>();
while (j < s.length()) {
if (!substring.containsKey(s.charAt(j))) {
maxLongest = Math.max(maxLongest, j - i + 1);
substring.put(s.charAt(j), j);
j++
} else {
// 取出重複字元的 index
int duplicateIndex = substring.remove(s.charAt(j));
// 因為我們只會移除掉上次重複字元的記錄
// 所以 Map 中重複字元的 index 可能是在 [i, j) 之前
// 如果是這樣我們就不移動 i, 表示其實本次 [i, j) 的 window 內沒有重複字元
// 但如果重複字元 index >= i 表示落在 [i, j] 中
// 因為我們新的 window 已不包含重複的字元
// 我們就以重複字元 index + 1為新的起點 i
int i = Math.max(substring.remove(s.charAt(j), i);
}
}
return maxLongest;
}
}
```
###### Java Code 2 (LeetCode Solution)
```java=
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0;
int j = 0;
int maxLongest = 0;
Map<Character, Integer> substring = new HashMap<>();
while (j < s.length()) {
if (substring.containsKey(s.charAt(j))) {
i = Math.max(substring.get(s.charAt(j)), i);
}
maxLongest = Math.max(maxLongest, j - i + 1);
// 這裡我們放入的時候 + 1 是為了之後發現重複字元取出時
// Math.max(s.charAt(j), i) 這裡就可以直接處理 3 種情況
// 1. 假設 s.charAt(j) < i, 表示重複字元不在 [i, j] 中, 不改變 window
// 2. 假設 s.charAt(j) >= i, 我們應該用重複字元 index + 1 為新的 window 的起點
substring.put(s.charAt(j), ++j);
}
return maxLongest;
}
}
```
- 如果字元有確定範圍，比方一定為 A-Z，則我們可以用陣列儲存每個字元的 index 位置，而儲存時放的位置可以用字元的 ASCII code
- 時間複雜度：因為我們不用一個個慢慢移動 window 的起始位置，所以每個元素只會被存取到 1 次，因此為 $O(N)$
- 空間複雜度：和解決方法 2 相同
Sign in with Wallet
Connect another wallet