[解題筆記] LeetCode: Longest Substring Without Repeating Characters (Medium)

前言

我其實不太常刷題，這陣子因為面試開始練手感，後來想想只是解題好像有點可惜，應該紀錄一下自己解題的思維，留一個機會讓未來我可以檢視自己有沒有進步；一方面開始練習寫文章，撰文真的好難。

前一陣子摸了基礎的 counter、pointer 用法之後，以為自己面對一些基礎的 algorithm 應該要秒解才對，結果還是花了比預期還要長的時間。我認為就是還不夠熟練，大部分演算法也不是一個公式就可以帶入得到解答，瞭解特定演算法的思維再判斷不同的情境才能順利解題。

題目

Given a string s, find the length of the longest substring without repeating characters.

Example:

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.

暴力解

如果沒有 pointer 的概念的話，大概就只能列舉出所有的 substring 組合，並且在每個組合內再跑迴圈檢查是否有重複字串。所以至少需要兩個迴圈來把所有的組合都找出來，然後再執行一個迴圈判斷 substring 有沒有重複，時間複雜度為 𝑂(𝑛³)（彷彿已經聽見 run test 時筆電風扇在轉的聲音）

var lengthOfLongestSubstring = function(s) {
  if (!s.length) return 0;

  let maxLeng = 0

  // 檢查所有的組合
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (checkRepeat(s.slice(i, j))) {
        maxLeng = Math.max(maxLeng, j - i + 1);
      }
    }
  }

  // 檢查重複
  checkRepeat(str) {
    let map = {}
    for (let s = 0; s < str.length; s++) {
      if (!map[str[s]]) {
        map[str[s]] = true;
      } else {
        return true;
      }
    }
    return false;
  }

  return maxLeng;
}

以前我都會認為「反正先把邏輯寫出來再慢慢優化」就直接暴力解，然後寫完也不知道從何優化起，因為一開始方向不對了啊！現在想想暴力解真的是打咩，發現技術跟心境都有慢慢進步也算是蠻欣慰的⋯

分析

盡力用我很爛的中文以一句話描述題目大概是：

回傳字串 s 當中，最長且不重複的字串長度。

關鍵字明顯是「longest」、「without repeating characters」

第一直覺想到用 map 來找出不重複的字。再來思考最長的長度時有點小卡住，一開始猜想應該是用 pointer，會有兩個指針分別紀錄 start & end，寫出雛型才想起來這就是 Sliding Window 啊。

OK，所以我需要一個物件作為 map，兩個 pointer 以及一個紀錄 maxLength 的變數。接著是邏輯，我用列表的方式把判斷條件列出（其實是不太會寫 pseudocode QQ）：

• 指針 r 從 index 0 開始往右找，並將跑過的字符紀錄在 map 當中。
• 檢查 l 與 r 之間的長度是不是大於 maxLeng ？如果是就更新 maxLeng。
• 如果字符已經在出現過了，map 要移除 l 位置的字符，然後 l 要右移。

統整這些條件後，完整程式碼就出生了：

var lengthOfLongestSubstring = function(s) {
  if (!s.length) return 0;

  let map = {};
  let l = 0;
  let r = 0;
  let maxLeng = 0;

  while (r < s.length) {
    if (!map[s[r]]) {
      map[s[r]] = true;
      if (r - l + 1 > maxLeng) {
        maxLeng = r - l + 1;
      }
      r++;
    } else {
      delete map[s[l]];
      l++;
    }
  }

  return maxLeng
};

使用 Sliding Window 時間複雜度為 𝑂(𝑛)。

更好的解法

有寫過 LeetCode 都會知道當你 Submit 答案且通過測試後，LeetCode 會有 Submission Detail 分析你提交的答案，告訴我們花費的時間與記憶題分別優於其他解答多少百分比，以此判斷我們提交的解答是不是還有優化空間。

有一些刷題網站會有討論區，當中就會有人分享自己的寫法 faster than 99.99% 就會好奇看一下是不是有什麼驚為天人的 idea，但也是遇過不少人故意寫來亂的就是了。

後來發現官方也有提供解答方案，其中就有提到 Sliding Window，但還有一個 Sliding Window Optimized 興奮如我必定要來分析紀錄一下還有什麼肉可以啃。

---

優化參考只有 Java 與 python 的版本，我把它轉為 Javascript 後如下：

var lengthOfLongestSubstring = function(s) {
  if (!s.length) return 0;

  let map = {};
  let l = 0;
  let r = 0;
  let maxLeng = 0;

  while (r < s.length) {
    if (map[s[r]]) {
      l = Math.max(map[s[r]], l)
    }    
    maxLeng = Math.max(maxLeng, r - l + 1);
    map[s[r]] = r + 1;
    r++;
  }
  
  return maxLeng
};

這個優化的關鍵在於 map 儲存的是字符的 index，而我的原始寫法只是紀錄字符有沒有出現過。差異在於我只能判斷有或沒有，而紀錄 index 可以直接跳過中間不必再檢查的部分。

// input: [ A E T C G B C H R ]
// map: { A: 1, E: 2, T: 3, C: 4, G: 5, B: 6 }
A E T C G B C H R
↑           ↑
// 遇到了第二個 [C]，原本在 [A] 位置的指針可以直接移到第一個 [C] 之後

// map: { A: 1, E: 2, T: 3, C: 7, G: 5, B: 6 }
A E T C G B C H R
        ↑   ↑

// 一步一步拆解開就會變這樣..
.. A E T C G B C ..
 [   E T C G B C ] 
 [     T C G B C ] // 節省這三步的判斷
 [       C G B C ]
           G B C

儲存 r 的時候有先 +1 再存，應該是為了避免 index 為 0 時 if (map[s[r]]) 會被判定為 false 的緣故。運用 HashMap 的概念，當有字符重複時就直接將 l 指定為先前紀錄的 index 的下一個位置（儲存之前已經 +1 過了），這樣就可以跳過中間不需要重複判斷的部分。

---

另一個我發現的小技巧是以 Math.max 來取代 if。好處是減少使用一個比較運算符（operator）版面也變得更簡潔，但邏輯不變。l 的計算也改用 Math.max 來取代。

// 如果 a > b 就讓 b 的值更新為 a
if (newValue > maxLeng) {
  maxLeng = newValue;
}
// 等同於
maxLeng = Math.max(maxLeng, newValue);

---

優化後的時間複雜度一樣是 𝑂(𝑛)。兩者的差異在於最糟的情況下(the worse case)：

• 一般的 Sliding Window 時間複雜度為 𝑂(2𝑛)
• 優化後 Sliding Window 時間複雜度為 𝑂(𝑛)

但這邊只是想做個簡單的紀錄，就不深究 Big O 相關的定義。

總結

我一直把 Sliding Window 當作 pointer 的變體或延伸應用來看，但實際上比起 counter、pointer 好像更需要一些畫面的想像力，這樣在跑邏輯的時候應該更容易明白現在跑到哪一步了，下一步又是什麼情況。（*Heap Sort：有人提到想像力嗎？）

希望自己解題筆記的系列可以持續，也希望今年可以進步到有能力寫技術文章，就不把它當作什麼新年願望了，第一步踩下去持續做才會有收穫。

參考資料

• Longest Substring Without Repeating Characters @LeetCode
• Subarrays with K Different Integers @LeetCode
• Maximum Erasure Value @LeetCode