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

剑指 Offer 48. 最长不含重复字符的子字符串https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

长度为 N的字符串共有 (1 + N)N/2个子字符串（复杂度为 O(N^2)，判断长度为 N的字符串是否有重复字符的复杂度为 O(N) ，因此本题使用暴力法解决的复杂度为 O(N^3)

考虑使用动态规划降低时间复杂度。

'''
#动态规划+字典
class Solution:
    def lengthOfLongestSubstring(self, s):
        if not s:return 0
        dic={}
        dp=[0]*len(s)
        dp[0]=1
        dic[s[0]]=0
        ans=1
        for j in range(1,len(s)):
            i=dic.get(s[j],-1)
            if i==-1:
                dp[j]=dp[j-1]+1
                ans=max(ans,dp[j])
                dic[s[j]]=j
            elif dp[j-1]<j-i:
                dp[j] = dp[j - 1] + 1
                ans = max(ans, dp[j])
                dic[s[j]] = j
            else:
                dp[j] =j-i
                ans = max(ans, dp[j])
                dic[s[j]] = j
        return ans
'''
'''
简化代码
class Solution:
    def lengthOfLongestSubstring(self, s):
        if not s: return 0
        dic = {}
        dp = [0] * len(s)
        dp[0] = 1
        dic[s[0]] = 0
        ans = 1
        for j in range(1, len(s)):
            i = dic.get(s[j], -1)#查找字典中有没有这个键
            if dp[j - 1] < j - i:
                dp[j] = dp[j - 1] + 1
                ans = max(ans, dp[j])
                dic[s[j]] = j
            else:
                 dp[j] = j - i
                 ans = max(ans, dp[j])
                 dic[s[j]] = j
        return ans
'''
#动态规划+线性遍历
class Solution:
    def lengthOfLongestSubstring(self, s):
        if not s: return 0
        dp = [0] * len(s)
        dp[0] = 1
        ans = 1
        for j in range(1, len(s)):
            i=j-1
            while i>=0 and s[i]!=s[j]:
                i-=1
            if dp[j - 1] < j - i:
                dp[j] = dp[j - 1] + 1
                ans = max(ans, dp[j])
            else:
                 dp[j] = j - i
                 ans = max(ans, dp[j])
        return ans

a=Solution()
nums="abcabcbb"
print(a.lengthOfLongestSubstring(nums))