无重复字符的最长子串

LeetCode 3 题

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

给定 "abcabcbb"，没有重复字符的最长子串是 "abc"，那么长度就是3。

给定 "bbbbb"，最长的子串就是 "b"，长度是1。

给定 "pwwkew"，最长子串是 "wke"，长度是3。请注意答案必须是一个子串，"pwke" 是子序列而不是子串。

分析

思路： 从左往右扩展子串，通过 2 个变量 i 和 j 来维持一个新的子串，j 不断移动，每加入一个新的字符，判断是否有重复的，如果有重复的则移动 i，生成新子串…

这里有个问题就是，如何判断子串中是否有重复的字符，传统思路就是循环，这样每次查找重复的时间复杂度为 O(n)，导致整体时间复杂度为 O(N^2)，其实通过使用 hashmap 可以保证每次查找的效率为 O(1)。

使用 go 语言实现：

func lengthOfLongestSubstring(s string) int {
    maxLength := 0
    i := 0
    m := make(map[rune]int)

    for j, v := range []rune(s) {
        if last, ok := m[v]; ok {
            i = last + 1
        }
        m[v] = j
        if j-i+1 > maxLength {
            maxLength = j - i + 1
        }
    }
    return maxLength
}