查找最大不重复子串的长度

查找最大不重复子串长度是一个常见的字符串处理问题，有多种解决思路。以下是几种常见的思路以及它们各自的时间和空间复杂度对比：

下面以滑动窗口为例，介绍下如何通过滑动窗口来查找最大不重复子串长度，该方法是一种有效的解决子串问题的策略。以下是对实现思路的详细分析：

1.滑动窗口：•窗口的起始位置由指针 start 控制，窗口的结束位置由指针 end 控制。初始时，窗口为空，即 start = 0，end = 0。•窗口会动态地扩展和收缩，通过调整 start 和 end 的位置，以找到最大不重复的子串。2.哈希表记录字符最后出现位置：•使用哈希表 charIndex 记录每个字符最后出现的位置。这样，当发现重复字符时，可以通过查表得知上一次出现的位置，从而更新 start。3.扫描字符串：•从左到右扫描字符串，每次迭代都进行以下步骤：•如果当前字符已经在窗口中，即 s[end] 在 charIndex 中存在，且其上一次出现位置大于等于 start，则更新 start 为上一次出现位置的下一个位置。•更新当前字符在 charIndex 中的位置为当前位置 end。•计算当前窗口的长度 currentLength = end - start + 1，并更新最大长度 maxLength。4.时间复杂度分析：•由于每个字符最多只会被访问两次（一次扩展，一次收缩），算法的时间复杂度是 O(n)，其中 n 是字符串的长度。5.空间复杂度分析：•空间复杂度主要取决于哈希表 charIndex 的大小，由于字符集是有限的，因此空间复杂度也是 O(字符集大小)。在实际情况下，字符集通常是常数级别，因此可以认为空间复杂度是 O(1)。

下面以Go为例，对上面的思路进行实现：

package main

import (
    "fmt"
)

func lengthOfLongestSubstring(s string) int {
    charIndex := make(map[byte]int)
    start := 0
    maxLength := 0

    for end := 0; end < len(s); end++ {
        // 如果字符已经在窗口中，更新窗口起始位置
        if lastIndex, found := charIndex[s[end]]; found && lastIndex >= start {
            start = lastIndex + 1
        }
        // 更新字符的最后出现位置
        charIndex[s[end]] = end
        // 更新最大长度
        if currentLength := end - start + 1; currentLength > maxLength {
            maxLength = currentLength
        }
    }

    return maxLength
}

func main() {
    input := "abcabcbb"
    result := lengthOfLongestSubstring(input)
    fmt.Printf("最大不重复子串的长度：%d\n", result)
}

在这个示例中，lengthOfLongestSubstring函数接收一个字符串作为输入，返回该字符串中最大不重复子串的长度。算法使用了一个哈希表charIndex来记录每个字符最后出现的位置，以及两个指针start和end维护滑动窗口的范围。

在每一步迭代中，如果字符已经在窗口中，更新窗口的起始位置为字符上一次出现的位置的下一个位置。然后，更新字符的最后出现位置，并计算当前窗口的长度，更新最大长度。

声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)[1]进行许可，使用时请注明出处。 Author: mengbin[2] blog: mengbin[3] Github: mengbin92[4] cnblogs: 恋水无意[5] 腾讯云开发者社区：孟斯特[6]

References

[1] 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0): https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh [2] mengbin: mengbin1992@outlook.com [3] mengbin: https://mengbin.top [4] mengbin92: https://mengbin92.github.io/ [5] 恋水无意: https://www.cnblogs.com/lianshuiwuyi/ [6] 孟斯特: https://cloud.tencent.com/developer/user/6649301