Leetcode題庫——3.無重複字元的最長子串

@author: ZZQ

@software: PyCharm

@file: lengthOfLongestSubstring.py

@time: 2018/9/18 20:35

要求：給定一個字元串，找出不含有重複字元的最長子串的長度。

e.g.: 輸入: "abcabcbb"

輸出: 3

解釋: 無重複字元的最長子串是 "abc"，其長度為 3。

輸入: "bbbbb"
      輸出: 1
      解釋: 無重複字元的最長子串是 "b"，其長度為 1。

      輸入: "pwwkew"
      輸出: 3
      解釋: 無重複字元的最長子串是 "wke"，其長度為 3。
    !  請注意，答案必須是一個子串，"pwke" 是一個子序列 而不是子串。
           

思路： 使用一個字典來存儲字元串中出現的每個字元在字元串中最近一次出現的索引，用一個整數來存儲最近出現重複的下标位置。

每次判目前字元是否發生了重複并且哦按段重複位置是否比之前記錄的位置大，如果是則更新。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        s_len = len(s)
        if s is None or s_len == 0:
            return s_len
        max_sub_str_len = 0
        currentRepeatIndex = 0
        everySnearestIndex = {}
        for i in range(s_len):
            if s[i] in everySnearestIndex and everySnearestIndex[s[i]]>=currentRepeatIndex:
                currentRepeatIndex = everySnearestIndex[s[i]] +1
            current_sub_str_len = i-currentRepeatIndex+1
            everySnearestIndex[s[i]] = i  # refresh the index of s[i]
            max_sub_str_len = max(max_sub_str_len, current_sub_str_len)
        return max_sub_str_len
           

CV小蠟肉