LeetCode如何找出最長不含重復字符的子字符串

題目描述

請從字符串中找出一個最長的不包含重復字符的子字符串，計算該最長子字符串的長度。

• s.length <= 40000

題目樣例

示例

• 輸入: "pwwkew"
• 輸出: 3
• 解釋: 因為無重復字符的最長子串是  "wke"，所以其長度為 3。請注意，你的答案必須是 子串 的長度，"pwke"  是一個子序列，不是子串。

題目思考

1. 如何通過一次遍歷得出結果?
2. 如果統(tǒng)計當前子字符串的字符種類?

解決方案

思路

• 分析題目, 一個最簡單的思路就是暴力法: 固定子字符串起點, 然后往后擴展, 因為不能含有重復, 所以可以使用集合統(tǒng)計當前子字符串的字符種類, 直到發(fā)現(xiàn)重復字符或者到終點停止, 取最長的子字符串作為結果. 但這樣需要兩重遍歷, 時間復雜度達到 O(N*C) (C 是字符的種類數(shù)目, 因為找到重復就會停下來, 所以不是 N^2), 不是很優(yōu)
• 基于暴力法進行分析, 假設當前子字符串起點是 start, 發(fā)現(xiàn)重復字符的位置是 end, 然后對應的該字符上個下標是 dup, 顯然 start <= dup < end
• 此時暴力法的做法是將 start+1 重新開始遍歷子字符串, 但這樣做完全沒有必要, 因為以 [start+1, dup]中的任一下標作為起點的字符串肯定都會在 end 處停下來, 因為找到了重復的(end 和 dup), 而且這些子字符串長度必然小于以 start 為起點的
• 所以更優(yōu)化的做法是 將起點向后遍歷到 dup+1, 從字符集合中移除遍歷過程中的字符, 然后將 dup+1 作為新的起點, 終點繼續(xù)從 end 處開始遍歷, 直到再次遇到重復字符, 重復上述步驟即可
• 這樣起點和終點都只需要遍歷一遍, 相比暴力法有所優(yōu)化
• 以上就是典型的滑動窗口的思想, 通常做法就是維護雙指針代表窗口起點和終點, 然后根據(jù)當前窗口是否滿足要求來進行不同的處理
• 下面的代碼對必要步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度 O(N): 起點和終點都只需要遍歷一遍
• 空間復雜度 O(1): 只使用了幾個變量

代碼

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 滑動窗口+當前字符集合, 時刻更新res
        start = 0
        res = 0
        v = set()
        for end in range(len(s)):
            c = s[end]
            if c in v:
                # 發(fā)現(xiàn)重復了, start向后遍歷找dup下標(即上一個c的下標)
                while start < end and s[start] != c:
                    v.remove(s[start])
                    start += 1
                # 此時dup = start, 需要將dup+1作為新的起點
                start += 1
            else:
                # 沒有重復, 將當前字符加入字符集合中
                v.add(c)
                # 最大子字符串長度就是最大的字符集合的長度, 當然此處也可以用end-start+1代替
                res = max(res, len(v))
        return res