Image From LeetCodeImage From LeetCode

今天我們要講解的是 [Longest Substring Without Repeating Characters]，這在 LeetCode 算是比較中階的題目，讓我們一起開始吧！

進來之前請先注意，我的方式不一定完全正確，只是依照我自己的理念進行撰寫，所以如果程式上有什麼更好的解法，歡迎提出見解。

這次題目

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

** Example 1 **

1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

** Example 2 **

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

** Example 3 **

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

自己解法

剛開始解這題時有點看不太懂題目，接著透過他的引導大概了解這個題目的意思，簡單來說他給你一個字串，你要比對字元尋找不重複的且最長的長度，例如上方的 Example 1 輸入abcabcbb，就會篩選掉重複的取得abc，為最常字元，而 Example 2 就不用說只有一個b是不重複的值，接著看到讓我懊惱的 Example 3，在思考他的不重複值為什麼不是pwke而是wke，這裡就是重點，也就是說他不是要你找出裡面有哪些字是不重複，而是連結的字串中哪在不重複。

舉例來說當起始點為0，結束點為5，他會抓出”pwwkew”的字，但發現裡面的ww有重複，所以放棄，接著起始點為0，結束點為4，會抓出pwwke，但也發現ww重複，那這次起始點為2，結束點為4，會抓出wke，此時裡面數字元沒有任何重複，因此我們就可以推斷，他是我們需要的值，接著進行回傳，最後找出最長的點即可。

根據官方第一組解法，他會顯示可以透過兩層For迴圈來解這題，索性就依照他的方式，不過官方是使用Java，我們要把他轉為Javascript來解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  // 字串最大長度
  let maxLength = s.length;
  // 最後最長的數值
  let ans = 0;

  // 起始點
  for (let i = 0; i < maxLength; i++) {
    // 結束點
    for (let j = i + 1; j <= maxLength; j++) {
      // 進行比對
    }
  }
  // 回傳最長的數字
  return ans;
};

接著我們建立一個函式，讓他去比對當下的字串例如i = 0,j = 5,取得字串是pwwkew，接著進行呼叫確認，假設如果沒有重複就回傳正確，並且確認當下的ans是不是最大，最大的話就讓他改變值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  // 字串最大長度
  let maxLength = s.length;
  // 最後最長的數值
  let ans = 0;

  // 起始點
  for (let i = 0; i < maxLength; i++) {
    // 結束點
    for (let j = i + 1; j <= maxLength; j++) {
      // 進行比對
      if (allUnique(s, i, j)) {
        // 如果比ans還要大進行更新
        ans = Math.max(ans, j - i);
      }
    }
  }
  // 回傳最長的數字
  return ans;
};

function allUnique(s, startIndex, endIndex) {
  // 目前陣列所擁有的字元
  let info = [];
  for (let i = startIndex; i < endIndex; i++) {
    // 取得某個單一字元例如p or w
    let ch = s.charAt(i);
    // 確認是否有重複的，如果有包含在陣列內就回傳失敗
    if (info.includes(ch)) return false;
    // 把字元丟到陣列裡並且為接下來的比對更新
    info.push(ch);
  }
  // 最後發現沒有重複即可更新
  return true;
}

如此一來就到功告成，透過Run Code也正確表現成功的字樣，另外我還多做測試丟到Code Pen去測試，也都正常，索性就進行提交。

Code PenCode Pen

不過我們提交後，可能會發生一個問題，官方回傳Time Limit Exceeded，似乎官網使用一個比較大的數值導致處理太久進而出錯，因為透過雙迴圈處理的複雜度相對變高，所以我們要嘗試另一個寫法！登登登～

這個題目讓我想到第一個題目Two Sum的解法，嘗試把執行過的值丟入物件裡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let maxLength = s.length;
  let ans = 0;
  let stringMap = [];
  for (let i = 0, j = 0; j < maxLength; j++) {
    let charText = s.charAt(j);
    // 如果裡面有存在資料的話進行進位
    if (stringMap[charText]) {
      //  i 就進位
      i = Math.max(stringMap[charText], i);
    }
    // 針對現在的點取最大長度
    ans = Math.max(ans, j - i + 1);
    // 丟到物件裡面，確認接下來可排除的重複值
    stringMap[charText] = j + 1;
  }
  return ans;
};

實作結果

最後再提交就能得出下面的結果，這題也是重複考驗物件的概念跟複雜度的問題，對於我這半路出家的小工程師來說也有點挑戰性，不過說不定有其他解法？如果有更好的解法歡迎一起討論，我們下一個挑戰見！

Longest Substring Without Repeating CharactersLongest Substring Without Repeating Characters