剑指offer面试题48: 最长不含重复字符的子字符串

Ryan_OVO

发布于 2023-10-18 20:27:13

1620

发布于 2023-10-18 20:27:13

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 maxLength


if __name__ == "__main__":
    s = 'arabcacfr'
    ss = Solution()
    print(ss.lengthOfLongestSubstring(s))

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-02-20，如有侵权请联系 cloudcommunity@tencent.com 删除

存储