题解 | #找到字符串的最长无重复字符子串#

# 说到【最长】第一想法就是动规；【去重复】第一想法就是哈希
# 题目：无重复的子序列长度
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr ):
        # write code here
        """
        # 状态定义：以arr[i]结尾的最长子串长度为dp[i]
        dp = [1] + [0] * (len(arr)-1)
        mark = 0 # 寻找最长子串的开头位置
        # 遍历整个串
        for i,s in enumerate(arr):
            for j in range(mark, i):
                if s == arr[mark]:
                    mark = j + 1 # mark 是从上一个状态开始变的，不用从头考虑
                dp[i] = i - mark + 1
        return max(dp)
        """
        dic = {}
        res = tmp = 0
        for j in range(len(arr)):
            i = dic.get(arr[j], -1)
            dic[arr[j]] = j
            tmp = j - i if tmp >= j - i else tmp + 1
            res = max(res, tmp)
        return res          

# 题目分析：
# 长度为n的字符串共有n(n+1)/2个子字符串（复杂度为O(n^2)
# 判断长度为n的字符串是否有重复字符的复杂度为O(n)
# 因此本题使用暴力法解决的复杂度为O(n^3)
#
# 状态定义：dp[i]表示以str[i]结尾的最长不重复子串的个数
# 状态转移：添加新字符，dp[]
# 状态初始化：dp[0]=1
# 是否包含重复字符如何判断?选择使用两个下标变量表示
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dp, j = [1] + [0] * (len(s) - 1), 0  # 用于比较i之前的元素是否与i所指元素一致
        if s == '':
            return 0
        for i in range(1, len(s)):
            # 每新加一个字符，就需要判断该字符是否在s[j:i]中包含，若不包含j不变，若包含j,那么j移动到下一个字符
            for k in range(j, i):
                if s[i] == s[k]: j = k + 1
            dp[i] = i - j + 1
            print(i, j, dp)
        return max(dp)


# 虽然解出来了，但是没有找到状态转移公式：dp[i]=dp[i-1]+1 if dp[i-1]<j-i else i-j
# 并且时间复杂度为O(n^2),空间复杂度O(n)可以用tmp来降低
# 本题比较关键的点就是找前面子串中是否出现过当前字符，并且找出该字符的位置。（我的方式时遍历前面的子串）

# 可以通过哈希表来存储各个字符出现最后一次的位置
class Solution1:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}  # 用于寻找重复出现的字符
        res = tmp = 0  # 取代dp数组造成的空间复杂度
        for j in range(len(s)):  # 右边界（新添字符位置）
            i = dic.get(s[j], -1)  # 获取左边界i
            dic[s[j]] = j  # 更新哈希表
            tmp = tmp + 1 if tmp < j - i else j - i  # 状态转移
            res = max(res, tmp)
        return res


print(Solution1().lengthOfLongestSubstring('abcabcbb'))