【LeetCode】0003. Longest Substring Without Repeating Characters

| | |

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

Note
that the answer must be a substring, "pwke" is a subsequence and not a substring.


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
Input: "pwwkew"
Output: 3 
Explanation: The answer is `"wke"`, with the length of 3.


Related Topics: Hash Table、String

解題邏輯與實作

這題是給定一個字串，從中找出一最長子字串，且子字串中不包含重複字元。

Sliding Window

我這題使用 Sliding Window 來解，一開始將 start 與 end 指標指在起始位置（ index=0 ），每輪 end 指標移動一格納入一個新的字元，在納入新字元後，檢查新字元是否已經存於 Window 中。

若有，則更改 start 位置，將指標移動到第一個重複字元的下一個位置。若無，則 start 停留在原位，最後記錄總長度並結束此輪。直到字串輪巡結束後回傳最長長度。


理論上是這樣啦，不過實做上為了效能考量這邊使用了 HashMap 來記錄，實做步驟如下：

  1. 初始化一個 HashMap indexes ，用以記錄目前出現過的字元，與其對應的下標。

  2. 開始輪巡整個字串，每一輪讀入一個新的字元，若該字元存於 indexes，則判斷記錄的下標是大於 start ，若大於 start 則更新 start 所指向的位置。

  3. 每一輪結束時，記錄最長的長度並更新新字元於 indexes 所記錄的下標。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
   def lengthOfLongestSubstring(self, s: str) -> int:
      start = 0
      max_len = 0
      indexes = {}

      for idx, letter in enumerate(list(s)):
         if letter in indexes and start <= indexes[letter]:
            start = indexes[letter] + 1

         max_len =   max(idx-start+1, max_len)
         indexes[letter] = idx

      return max_len

其他連結

  1. 【LeetCode】0000. 解題目錄