查找最大不重复子串的长度
原创
查找最大不重复子串长度是一个常见的字符串处理问题，有多种解决思路。以下是几种常见的思路以及它们各自的时间和空间复杂度对比：
名称 | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
滑动窗口 | 维护一个滑动窗口，使窗口中的字符都是不重复的。通过两个指针 | O(n)，每个字符最多被访问两次，一次是窗口扩展，一次是窗口收缩。 | O(min(m, n))，其中 m 是字符集的大小，用于存储哈希表。在最坏情况下，字符集的大小可能是常数，因此空间复杂度是 O(1)。 |
动态规划 | 使用动态规划数组 | 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为例，对上面的思路进行实现：
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维护滑动窗口的范围。
在每一步迭代中，如果字符已经在窗口中，更新窗口的起始位置为字符上一次出现的位置的下一个位置。然后，更新字符的最后出现位置，并计算当前窗口的长度，更新最大长度。
我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！
声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行许可，使用时请注明出处。
blog: mengbin
Github: mengbin92
cnblogs: 恋水无意
腾讯云开发者社区：孟斯特
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。