3. Longest Substring Without Repeating Characters

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. 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.

解題思路:

題目主要是找出 依序且不重複的最長字串。

pwwkew 可以找出 wke 是最長的字串。

看起來不難，所以寫了一個錯的解法…

def lengthOfLongestSubstring(s):
    index = 0
    sub_string = ""
    max_length = 1

    while True:
        if s[index] not in sub_string:
            sub_string += s[index]
        else:
            max_length = max(max_length, len(sub_string))
            sub_string = s[index]
        index += 1

        if index >= len(s):
            break
    return max(max_length, len(sub_string))

思路是，把這選取到的字串放在 sub_string 中，如果遇到重複的字串，就把目前的 sub_string 與 max_length 比較，如果 sub_string 比較長，就更新 max_length。

看起來很正常，畢竟 “abcabcbb” 就是 “abc” 、 “pwwkew” 就是 “wke”。 都是拿重複那個字之後的字串繼續跑，Submit 之後才發現，如果是 dvdf 就爆了，這演算法只會找到 dv 或 df，但實際答案是 vdf。

所以正解應該是要用 滑動窗口 的方式來解題。 正確思路是這樣的…

我們給予一個陣列稱 walked 好了，這陣列會記錄現在走過的字元 然後我們給予兩個指標 left 與 right，left 代表目前的字串的開頭，right 代表目前的字串的結尾 透過 right 來遍歷整個字串，如果 s[right] 不在 walked 中

這時會發現，如果 walked 中 s[right] 走過了該怎麼辦？

d v d f
l   r

當 r 在 d 上，walked 裡又有 d 時，我們就必須讓 left 走到沒有 d 的地方(walked 也要隨著修正成[v])，這樣就不重複了！

d v d f
  l r

最後找出 walked 的最大長度即可。

def lengthOfLongestSubstring(s):
    left = 0
    right = 0
    max_length = 0

    walked = []
    while right < len(s):
        while (s[right] in walked):
            walked.pop(0)
            left += 1
        walked.append(s[right])

        max_length = max(max_length, len(walked))
        right += 1
    return max_length