Try   HackMD

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:

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

Example 2:

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

Example 3:

Input: "pwwkew"
Output: 3 
Explanation: The answer is `"wke"`, with the length of 3. 

Related Topics: Hash TableString

解題邏輯與實作

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

Sliding Window

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

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


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

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

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

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

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. 解題目錄



本文作者: 辛西亞.Cynthia
本文連結辛西亞的技能樹 / hackmd 版本
版權聲明: 部落格中所有文章,均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處!