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

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

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

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)进行许可，使用时请注明出处。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 恋水无意
腾讯云开发者社区：孟斯特