3. Longest Substring Without Repeating Characters

最长的没有重复字符的字符串长度

思路： 没有重复字符的子字符串为一个目标字符串，遍历所有字符，记录字符到索引的映射，如果一个字符在目标子串中且其下标比目标子串的起始下标大，则需要更新目标子串的起始下标，不断比较并获取最大的长度

复杂度：O(n)

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 6 star, 遍历字符串，使用字典记录每个字母到索引的映射
        rs, start = 0, 0
        memo = {}
        for index, v in enumerate(s):
            # 当前字母不在s[start:index]范围内，可以继续向前遍历
            if v not in memo or memo[v] < start:
                rs = max(rs, index + 1 - start)
            # 当前字母在s[start:index]有重复，新的起点从重复字母索引的下一位开始
            else:
                start = memo[v] + 1
            memo[v] = index
        return rs

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func lengthOfLongestSubstring(s string) int {
    start := 0
    max := 0
    memo := make(map[string]int)
    for index := 0; index < len(s); index++ {
        c := string(s[index])
        val, ok := memo[c]
        if ok && val >= start {
            start = val + 1
        }
        memo[c] = index
        if index +1 - start > max {
            max = index +1 - start
        } 
        
    }
    return max
    
}