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

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

名称	思路	时间复杂度	空间复杂度
滑动窗口	维护一个滑动窗口，使窗口中的字符都是不重复的。通过两个指针`start`和`end`控制窗口的范围，动态调整窗口的大小，以找到最大不重复子串。	O(n)，每个字符最多被访问两次，一次是窗口扩展，一次是窗口收缩。	O(min(m, n))，其中 m 是字符集的大小，用于存储哈希表。在最坏情况下，字符集的大小可能是常数，因此空间复杂度是 O(1)。
动态规划	使用动态规划数组`dp`，其中`dp[i]`表示以字符`s[i]`结尾的最长不重复子串的长度。通过状态转移方程更新`dp[i]`，并维护一个变量记录最大长度。	O(n)，需要遍历整个字符串。	O(m)，其中 m 是字符集的大小。需要额外的数组来存储动态规划状态。在最坏情况下，字符集的大小可能是常数，因此空间复杂度是 O(1)。
哈希表	使用哈希表记录字符最后出现的位置。在遍历字符串的过程中，通过查表得知字符上一次出现的位置，从而更新窗口的起始位置。	O(n)，需要遍历整个字符串。	O(min(m, n))，其中 m 是字符集的大小。需要存储哈希表。在最坏情况下，字符集的大小可能是常数，因此空间复杂度是 O(1)。
双指针	使用两个指针，分别指向子串的起始位置和结束位置。遍历字符串时，根据字符是否重复，动态调整两个指针的位置。	O(n)，需要遍历整个字符串。	O(min(m, n))，其中 m 是字符集的大小。在最坏情况下，字符集的大小可能是常数，因此空间复杂度是 O(1)。
集合/数组	使用集合或数组来存储窗口中的字符，判断字符是否重复。在遍历字符串时，根据字符是否在集合中，动态调整窗口的大小。	O(n)，需要遍历整个字符串。	O(min(m, n))，其中 m 是字符集的大小。在最坏情况下，字符集的大小可能是常数，因此空间复杂度是 O(1)。

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

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

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

代码语言：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("最大不重复子串的长度：%dn", result)
}

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

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

我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！

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

2024腾讯·技术创作特训营第五期

0 人点赞