[LeetCode 解題紀錄] 3. Longest Substring Without Repeating Characters
3. Longest Substring Without Repeating Characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Problem:
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.
Constraints:
0 <= s.length <= 5 * 104
s
consists of English letters, digits, symbols and spaces.
題意
這題的題意很明確,就是要找出最大不重複的子字串長度。
問題解析:
通常看到找子字串、或是找到子字串長度,有蠻高機率都是使用 sliding window / two pointers 的方法來解題,透過每回合紀錄當下最大值,來找到最佳解。
解法
暴力法
一樣可以先來看看最直覺的暴力法,暴力法要遍歷所有可能的子字串,檢查每個子字串是否包含重複字元,並記錄最大長度。這種方法的時間複雜度是 O(n³),因為需要三層迴圈:
- 外層兩層迴圈生成所有可能的子字串。
- 內層迴圈檢查每個子字符串是否包含重複字元。
var lengthOfLongestSubstring = function(s) {
let max = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j <= s.length; j++) {
let subStr = s.slice(i, j);
if (isUnique(subStr)) {
max = Math.max(max, subStr.length);
}
}
}
return max;
};
function isUnique(str) {
let set = new Set();
for (let char of str) {
if (set.has(char)) {
return false;
}
set.add(char);
}
return true;
}
- 時間複雜度:
O(n^3)
- 空間複雜度:
O(n)
Dynamic programming 動態規劃
這題也可以使用 DP 的方式來解,從剛剛的暴力法的想法出發,我們把每個位置處的最長不含重複字元的子字串記錄下來,利用查表發方式來降低重複的計算。
Dynamic programming 概念複習:
var lengthOfLongestSubstring = function(s) {
let n = s.length;
if (n == 0) return 0;
let max = 1;
let dp = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
let j = i - 1;
while (j >= 0 && s[i] !== s[j]) {
j--;
}
dp[i] = (j === -1) ? dp[i - 1] + 1 : i - j;
max = Math.max(max, dp[i]);
}
return max;
};
- 時間複雜度:
O(n^2)
- 空間複雜度:
O(n)
Sliding Window / Two Pointers
這題要找到最大(某條件下)子字串長度,最適合的還是使用 Sliding Window / Two Pointers 的解法,才會是最有效率的了。
Sliding Window / Two Pointers 概念複習:
- 使用兩個指針表示窗口的左邊界和右邊界,初始值都為 0。
- 右指針向右移動,擴展窗口,直到遇到重複字元為止。
- 當遇到重複字元時,左指針向右移動,收縮窗口,直到窗口內不再有重複字元。
- 在每次移動窗口時,記錄窗口的大小,並更新最大窗口大小。
- 重複步驟 2 和 3,直到右指針遍歷完整個字元串。
- 返回最大窗口大小作為結果。
而使用這種方法,還會有著你使用什麼來紀錄子字串的差異,我們可以使用一個字串 subStr 來記錄,也可以使用一個 Hash Set 來增加查找的速度。
使用字串作為紀錄:
var lengthOfLongestSubstring = function(s) {
let left = 0;
let max = 0;
let subStr = '';
for (let right = 0; right < s.length; right++) {
let index = subStr.indexOf(s[right]);
if (index === -1) {
subStr += s[right];
} else {
left = left + index + 1;
subStr = s.substring(left, right + 1);
}
max = Math.max(max, subStr.length);
}
return max;
};
使用 Hash Set 作為紀錄:
var lengthOfLongestSubstring = function(s) {
let left = 0;
let max = 0;
let charSet = new Set();
for (let right = 0; right < s.length; right++) {
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
max = Math.max(max, right - left + 1);
}
return max;
};
不過這兩個有什麼差異呢?這個會跟實作上的細節比較相關一點,因為使用 .indexOf
在查找的時候其實還是去做遍歷整個字串,所以最差情況也是會用到 O(n)
的時間。然而使用 Hash Set 的方式,就可以讓查找時間時間降低到 O(1)
(這裡只有指的是去看這個字元有沒有在子字串中的查找時間)。
兩種方法的空間複雜度都是 O(n)
,因為它們都需要存儲當前窗口的字元,因此在選擇寫法上,使用 Hash Set 來作為儲存子字串,再搭配 Sliding Window 的方式會是比較好的選擇。