Leetcode: https://leetcode.com/problems/longest-substring-without-repeating-characters/

[正文]

分析

這題就是直接掃過去，維護兩個 R 和 L 這兩個 index，每次向右移動 R，表示讀入一個新字母，若讀入的字母 s[R] 前面有出現過則更新 L 的值，沒有則不更動。然後每次去比對 length 和 R-L+1(目前長度) 的大小來更新最大長度值。

example

length = max(length, R - L + 1) = 2
a b a d c ...
L R
-------------------
length = max(length, R - L + 1) = 2
a b a d c ...
  L R                                 // 因為 s[R] 出現過，更新 L 值
-------------------
length = max(length, R - L + 1) = 3
a b a d c ...
  L   R
-------------------
...
-------------------
length = max(length, R - L + 1) = 10
... a b c d a ...
      L     R                         // 雖然 s[R] 出現過，但 index 比 L 還小，不用更新 L

確認的方式使用 hash 來存，這樣每次查詢就可以降到 $O(1)$;

Code

/**
 * @param {string} string
 * @return {number}
 */
var lengthOfLongestSubstring = function (string) {
  let maxLength = 0;
  let left = 0;

  let hash = Object.create(null);
  for (let right = 0; right < string.length; right++) {
    const character = string.charAt(right);

    left = Math.max(hash[character] || 0, left);
    maxLength = Math.max(right - left + 1, maxLength);
    hash[character] = right + 1;
  }

  return maxLength;
};

L = max( hash[s[R]] || 0, L ); 用來更新 L，如果前面沒出現過 hash[s[R]] = 0, 有出現過但 index 比 L 還小都不會更新到 L 的值;
hash[s[R]] = R + 1; 更新 hash 值，R+1 是因為 L 要更新成出現過的字母的後面一個

羊毛 | 寫 Code 雜談

LeetCode with JS - 0003 Longest Substring Without Repeating Characters

[正文]

分析

Code