Given a string s, find the length of the longest substring without repeating characters.
ex. A substring is a contiguous non-empty sequence of characters within a string.
給與一個字串 s,找出最長且不重複字元的子字串長度。
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.
solution:
1. 定義 charSet 是一個 Set() 集合,left 為 0,maxLength 為 0。
2. 運用 for 迴圈搭配 while 建立 sliding window。
3. 依序向右遍歷字串,當發現重複字串時,則 left 向右移動直到移除重複字串。
4. 每次窗口大小變動時,更新 maxLength。
Code 1: BigO(n) Sliding Window
function lengthOfLongestSubstring(s: string): number { let charSet: Set<string> = new Set(); let left: number = 0, maxLength: number = 0; for (let right = 0; right < s.length; right++) { while(charSet.has(s[right])) { charSet.delete(s[left]); left++; } charSet.add(s[right]); maxLength = Math.max(maxLength, right - left + 1); } return maxLength; };