Leetcode - Medium - 3. Longest Substring Without Repeating Characters - Javascript

Leetcode - Medium - 3. Longest Substring Without Repeating Characters - Javascript

   清晨6:57       Rain Lin

---

 3. Longest Substring Without Repeating Characters

Medium

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.

解題方向：

1. 這題主要是要找不重複字串中長度最長的數量

2. 可透過 hash table 方式紀錄字串出現時的 index

3. 當字母重複時即將 slide window 的 left 設定與重複字母的 index 相同, 並將最新的 index 記錄到重複字母中

4. 比對 slide window 的 left 與 right 間的距離是否為最大的長度

5. 結束時回傳最大長度的數量  時間複雜度 O(n)

程式碼 ：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let substring = '';
    let maxLen = 0;
    let hashTable = {};
    let leftIndex = 0;
    
    for (let i in s) {
        const rightIndex = parseInt(i) + 1;
        const letter = s[i];
        
        const letterIndex = hashTable[letter] ? hashTable[letter] : 0;
        leftIndex = leftIndex < letterIndex ? letterIndex : leftIndex;
        
        const interval = rightIndex - leftIndex;
        maxLen = maxLen < interval ? interval : maxLen;
        hashTable[letter] = rightIndex;   
    }
    
    return maxLen;
};

執行成果：