用 JavaScript 解 LeetCode — Longest Substring Without Repeating Characters
題目
這次的 LeetCode 題目是「找出沒有重複字母的最長子字串」，難度為 medium。
官方範例
- 輸入值: “abcabcbb”
- 輸出值: 3
- 說明: 最長的「子字串」為 “abc”, 長度是 3
關鍵點
- 如何有效找出所有可能的「子字串」
- 計算「最大子字串」的長度
- 判斷是否有「重複字母」
解題思路
1. Sliding Window 滑動視窗演算法
我使用 Sliding Window 演算法，來搜索出所有「符合條件的子字串」。
window (視窗) 在此是指 Input 字串中的一段範圍 (子字串)
通常用 start index 和 end index 兩個索引值，來記錄視窗的邊界。
目的：盡可能擴展視窗的大小，使「字母不重複」的「子字串」，範圍越長越好。
我們先從「第一個字母」開始 (start index = 0; end index = 0)
i. 擴展視窗的「右邊界」 (end index++)
當右邊界擴展到出現「重複字母」時，停下來，計算先前那段「沒有重複字母」的視窗長度，儲存起來
ii.接著，將視窗「左邊界」向右收縮 (start index++)，直到裡面沒有重複字母。
iii. 重複 i. ii. 步驟，直到視窗無法再向右滑動 (end index 已到底)，表示我們已搜索完所有「字母不重複的子字串」。
2. 計算「最大子字串」的長度
- 定義一個變數
maxLength - 把所有「字母不重複的子字串」的長度 (前面步驟 i 的計算結果) ，和
maxLength比較 - 取兩者較大的那個，更新至
maxLength
3. 使用 Set 儲存不重複的字母
Set (不重複集合)可以用來儲存「當前子字串」包含的所有字母。- 假設有一個
curSet的集合，儲存了當前視窗內所有字母。 - 當我們拿到一個新的字母
char，想判斷它是否為重複字母，用curSet.has(char)就能辦到。
舉例說明
以 Input String: pwwkew 為例，假設 startIdx 和 endIdx 分別為視窗的兩側邊界
endIdx = 0
‘p’wwkew
目前子字串：p，視窗邊界 [startIdx, endIdx] = [0, 0]
endIdx = 1
p‘w’wkew
目前子字串：pw，視窗邊界 [startIdx, endIdx] = [0, 1]
endIdx = 2
pw’w’kew
目前子字串：pww ->有重複字元， [startIdx, endIdx] = [0, 2]
- 更新 maxLength
將先前「合格子字串」(pw) 的長度記錄下來：maxLength = 2 - 視窗左邊界向右收縮
從視窗的最前面開始刪除字母，直到沒有重複字母為止：
- 刪除 p
目前子字串：ww，視窗邊界 [startIdx, endIdx] = [1, 2]
- 刪除 w
目前子字串：w （沒有重複字母），視窗邊界 [startIdx, endIdx] = [2, 2]
endIdx = 3
pww’k’ew
目前子字串：wk， [startIdx, endIdx] = [2, 3]
endIdx = 4
pwwk’e’w
目前子字串：wke， [startIdx, endIdx] = [2, 4]
endIdx = 5
pwwke’w’
目前子字串：wkew -> 有重複字母， [startIdx, endIdx] = [2, 5]。
- 更新 maxLength
將先前「合格子字串」(wke) 的長度記錄下來：3。我們發現他比maxLength 還大。因此更新 maxLength 為 3 - 視窗左邊界向右收縮
從子字串 wkew 的最前面開始刪除字母，直到字串沒有重複字母為止：
- 刪除 w
目前子字串：kew -> 沒有重複字母了，更新視窗邊界 [startIdx, endIdx] = [3, 5]
此時視窗已滑動至最右側 (endIdx = 5)，搜索完畢
- 得出「字母不重複的子字串」，最長為 3 (
maxLength)
程式碼
function lengthOfLongestSubstring(s) {
var startIdx = 0
var endIdx = 0
var maxLength = 0
var curSet = new Set()
for (let endIdx = 0; endIdx < s.length; endIdx++) {
if (curSet.has(s[endIdx])) {
var prevEndIdx = Math.max(endIdx - 1, 0)
maxLength = Math.max(prevEndIdx - startIdx + 1, maxLength)
while (s[startIdx] !== s[endIdx]) {
// 視窗左邊界向右收縮，更新 curSet
curSet.delete(s[startIdx++])
}
startIdx++ // 左邊界已指到重複字母的位置，往右再收縮一格
} else {
curSet.add(s[endIdx])
}
if (endIdx === (s.length - 1)) {
maxLength = Math.max(endIdx - startIdx + 1, maxLength)
}
}
return maxLength
};Reference
https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/