2021-06-24：求一个字符串中，最长无重复字符子串长度。

2021-06-24：求一个字符串中，最长无重复字符子串长度。

福大大 答案2021-06-24：

方法一：滑动窗口。自然智慧。
不重复的时候，右指针右移；重复的时候，左指针右移。

方法二：求出最右不重复位置。
map：key是值，value是数组序号，初始值value都是-1。

时间复杂度：O(N)。空间复杂度：O(不同字符个数)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    s := "moonfdd"
    ret1 := lengthOfLongestSubstring1(s)
    fmt.Println(ret1)
    ret2 := lengthOfLongestSubstring2(s)
    fmt.Println(ret2)
}

//方法一：滑动窗口。自然智慧。
func lengthOfLongestSubstring1(s string) int {
    // 哈希集合，记录每个字符是否出现过
    m := map[byte]int{}
    n := len(s)
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    rk, ans := -1, 0
    for i := 0; i < n; i++ {
        if i != 0 {
            // 左指针向右移动一格，移除一个字符
            delete(m, s[i-1])
        }
        for rk+1 < n && m[s[rk+1]] == 0 {
            // 不断地移动右指针
            m[s[rk+1]]++
            rk++
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = getMax(ans, rk-i+1)
    }
    return ans
}

//方法二：求出最右不重复位置。
func lengthOfLongestSubstring2(s string) int {
    if len(s) == 0 {
        return 0
    }
    indexList := make([]int, 256)
    for i := 0; i < 256; i++ {
        indexList[i] = -1
    }
    N := len(s)
    ans := 0
    p := -1
    for i := 0; i < N; i++ {
        p = getMax(p, indexList[s[i]])
        ans = getMax(ans, i-p)
        indexList[s[i]] = i
    }
    return ans
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func getMin(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

执行结果如下：