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

2024-01-30 13:40:37 浏览数 (1)

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

名称

思路

时间复杂度

空间复杂度

滑动窗口

维护一个滑动窗口，使窗口中的字符都是不重复的。通过两个指针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)。

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

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为例，对上面的思路进行实现：

代码语言：javascript复制
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维护滑动窗口的范围。

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

声明：本作品采用署名-非商业性使用-相同方式共享 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

指针 字符串 存储 遍历 数组

0 人点赞