最长无重复子字符串

发表于 | 分类于 |
最长无重复子字符串练习题

任务描述：对于一个字符串，设计一个算法，找到字符串的最长无重复子串长度

输入：”aabcb”, 5
返回：3

思路：先从第一个字符开始往后遍历，当遇到第一个重复字符时停止遍历，记录此时字符串长度。然后从第二个字符开始往后遍历，遇到重复字符时停止遍历，记录此时字符串长度，一直到最后从最后一个字符遍历。返回所有记录长度中最大的一个值。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class DistinctSubstring:
    def longestSubstring(self, A, n):
        # write code here
        max_len = 0
        for i in range(n):
            tem_str = ""
            tem_len = 0
            for j in range(i, n):
                if A[j] not in tem_str:
                    tem_str += A[j]
                    tem_len += 1
                    max_len = max(max_len, tem_len)
                else:
                    max_len = max(max_len, tem_len)
                    break
        return max_len