leetcode_3

发表于   |   分类于

Longest Substring Without Repeating Characters(最长不重复子串)

题目戳这

题意

求字符串中的最长不重复子串

解法

如果用暴力的方法就是O(n^2)的复杂度，会超时。这我们用一个比较巧妙的方法，就是用一个数组来记录某个字符最近出现的位置，比如字符出现在位置i，结果在位置j又出现了，那么这个子串的长度就是 j-i。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        slen = len(s)
        mp = {}
        id = -1
        max = 0
        for i in range(slen):
            if s[i] in mp and mp[s[i]] > id:
                id = mp[s[i]]
            if i - id > max:
                max = i - id
            
            mp[s[i]] = i
        
        return max