Given a string, find the length of the longest substring without repeating characters.(请从子字符串中找出一个最长的不包含重复字符的子字符串)

首先定义函数f(i)表示以第i个字符结尾的不包含重复字符的子字符串的最大长度。我们从左到右扫描字符串中的每个字符。当我们计算第i个字符时，我们已经知道了f(i-1)。

如果第i个字符之前在字符串中没有出现过，那么f(i)=f(i-1) + 1,显然f(0)=1.

如果第i个字符之前在字符串中出现过，那么情况就复杂点，我们先计算第i个字符和它上次出现在字符串中的位置的距离，并记为d,接着就有两种情况。第一种。d<=f(i-1)，此时，第i个字符出现在了f(i-1)对应的最长字符串中，因此f(i)=d。这种情况是能够保证字符是连续的。当我们在f(i-1)对应的最长字符串找到了第i个字符的位置索引，就删除f(i-1)对应的字符串下，i字符索引之前的所有字符。第二种情况，d>f(i-1)，此时第i个字符出现在了f(i-1)对应的最长字符串之前，那么依然有f(i)=f(i-1)+1

书上分析如下:

我在leetcode上找到一题最长子序列的

运行结果:

code:

class Solution:    def lengthOfLongestSubstring(self, s):        position = []  #  标记不重复的字符列表        char_distance = 0  # 第i 个字符与该字符上一次出现的距离        maxLength = 0  # 存储最长子序列        for index, x in enumerate(s):            if x not in position:                position.append(x)            else:                char_distance = len(position) - position.index(x)  # 计算距离                if char_distance <= len(position):                    position = position[position.index(x) + 1 :]                    position.append(x)                else:                    position.append(x)               if len(position) > maxLength:                maxLength = len(position)  # 找到最长的子序列, abcabcbb测试案例        return maxLengthif __name__ == "__main__":    s = 'arabcacfr'    ss = Solution()    print(ss.lengthOfLongestSubstring(s))