[LeetCode] 3. Longest Substring Without Repeating Characters

轉自 LeetCode

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

<Solution>

參考解答

這題需要動點腦筋

主要想法是用一個 window 去歷遍，window 由 left 和 right 定義其大小

如果沒遇到重複字元，right 就一直增加，left 不動

當遇到重複字元，left 就移動到此字元上次出現的位置

用個例子說明 : "abcdefcgh"

當還沒遇到第2個 c 之前，left初始為 -1，right 一直向右移

當 right 指到 f 時，此時 window 大小為 5 - (-1) = 6，也是目前的 longest substring

而當 right 指到第2個 c 時，發現是重複字元了

把 left 移到上一次 c 出現的地方，此時 window 的長度為 6 - 2 = 4

接著再重複步驟下去

而為什麼可以把 left 直接移動到上一次 c 出現的地方 (index 2)

因為從第2個 c 回頭看 substring 時，遇到第 1 個 c 的時候就會中斷

也就是說在第 1 個 c 之前的字元，是無法被計算到的

所以可以把 left 直接移動到上一次 c 出現的地方

過程中把最大的 window size 記錄下來，就是答案了

code 如下

c++

Java


Kotlin