title: 最长无重复子串
date: 2016-10-31 14:20:45

tags: 算法

对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。
测试样例：
“aabcb”,5
返回：3 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class DistinctSubstring:
    def longestSubstring(self, A, n):
        # write code here
        dic = {}
        pre = -1
        l = 0
        ltmp = 0
        for i in range(0,n):
            if not dic.has_key(A[i]):
                dic[A[i]] = i
                ltmp = i - pre
            else:
                if i - dic[A[i]] < i - pre:
                    ltmp = i - dic[A[i]]
                    pre = dic[A[i]]
                else:
                    ltmp = i - pre
                dic[A[i]] = i
            if ltmp > l:
                l = ltmp
        return l