剑指Offer 48.最长不含重复的子字符串(Python)

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。假设字符串中只包含‘a’~'z’的字符。
示例:

在字符串‘’arabcacfr‘’中,最长的不含重复字符的子字符串是‘’acfr‘’,长度为4.

解题思路 动态规划
class Solution:
    def longestSubstringWithoutDuplication(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s: return 0
        
        dic = {s[0]:0}
        res =[1]
        
        for i in range(1,len(s)):
            if s[i] not in dic:
                res.append(res[i-1]+1)
            else:
                res.append(min(i-dic[s[i]], res[i-1]+1))
            dic[s[i]] = i
            
        return max(res)

最新回复(0)
/jishuD52ja_2FwUIq_2BUU0_2Fd6cOjE28Dd0RwhpBcmp1wo6temBE_3D4858765
8 简首页