无重复字符的最长子串

难度:中等1

描述

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

题解

暴力法

会出现时间限制的错误即 TLE

思路

逐个检查所有的子字符串,看它是否不含有重复的字符。

算法

实现一个方法(函数,比如名为 allUnique,传入参数为 子字符串)用于判断子字符串是否包含重复字符,如果不包含重复字符,它会返回 true,否则会返回 false。遍历给定字符串 s 的所有可能的子字符串并调用函数 allUnique。 如果返回值为 true,那么我们将会更新无重复字符子串的最大长度。

那么现在主要考虑两个问题:枚举所有的子字符串和 allUnique 的实现。

  • 枚举所有的子字符串

    为了不额外增加太多空间复杂度,只需枚举子字符串在原字符串开始和结束的索引即可,分别记为 ij,满足 0\le i < j \le n。所以,使用 i 从 0 到 n-1 以及 ji+1n 两个签到的循环枚举字符串 s 的所有子串。

  • allUnique 的实现

    遍历字符串中所有的字符,逐个放入一个集合中,在放之前要检查集合是否包含字符,如果已经包含那就返回 false ,一直到循环结束如果都没有重复的,那就返回 true

实现

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var maxLen = 0
        for i in 0..<s.count {
            for j in (i+1)..<(s.count+1) {
                if self.allUnique(s, i, j) {
                    maxLen = max(maxLen, j - i)
                }
            }
        }
        return maxLen
    }

    func allUnique(_ s: String, _ start: Int, _ end: Int) -> Bool {
        var hashSet = [Character]()
        let startIndex = s.startIndex
        let subString = s[s.index(startIndex, offsetBy: start)..<s.index(startIndex, offsetBy: end)]
        for c in subString {
            if hashSet.contains(c) {
                return false
            }
            hashSet.append(c)
        }
        return true
    }
}
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        length = len(s)
        for i in range(length):
            for j in range(i + 1, length + 1):
                if self.all_unique(s, i, j):
                    max_len = max(max_len, j - i)
        return max_len

    def all_unique(self, s: str, start: int, end: int) -> bool:
        hash_set = []
        for i in range(start, end):
            c = s[i]
            if c in hash_set:
                return False
            hash_set.append(c)
        return True

复杂度分析

  • 时间复杂度:O(n^3)

    要验证索引范围在 [i,j) 内的字符是否都是唯一的,我们需要检查该范围中的所有字符。

    因此,它将花费 O(j-i) 的时间。

    对于给定的 i ,对于所有 j\in [i+1,n] 所耗费的时间总和是:

    \sum^n_{i+1}O{j-i}

    因此,执行所有步骤耗去的时间总和为:

    O(\sum^{n-1}_{i=0}(\sum^n_{j=i+1}(j-i)))=O(\sum^{n-1}_{i=0}\frac{(1+n-i)(n-i)}{2})=O(n^3)
  • 空间复杂度:O(min(m,n))

    我们需要 O(k) 的空间来检查子字符串中是否有重复字符,其中 k 表示集合的大小。而集合的大小取决于字符串的大小 n 以及字符集/字母的大小 m

滑动窗口

算法

暴力法会反复检查一个子字符串是否含有重复的字符,这是没有必要的。如果从索引 ij-1 之间的子字符串 s_{ij} 已经被检查为没有重复字符,只需要检查 s[j] 对应的字符是否已经存在于子字符串 s_{ij} 中就可以了。

要检查一个字符是否已经在子字符串中,我们可以检查整个子字符串,这将产生发一份复杂度为 O(n^2) 的算法,但我们可以做得更好。

使用滑动窗口可以只需 O(1) 的时间来检查字符是否在子字符串中。

滑动窗口是数组/字符串问题中常用的抽象概念。窗口通畅是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i,j) (左闭右开),滑动窗口是可以将两个边界向某个方向“滑动”的区间。例如将 [i,j) 向右滑动 1 个元素,则窗口就变成了 [i+1, j+1]

在我们这个问题中,使用集合 hashSet 存储存储窗口 [i, j) 中的字符(最初 j=i)。然后向右滑动索引 j,如果索引处的字符 s[j] 不在 hashSet 中,继续滑动 j,直到 s[j] 已经存在于集合中,此时没有重复字符的最长字符串将会以索引 i 开头,对所有的 i 重复做滑动处理,最终就会得到答案。

实现

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var maxLen = 0, i = 0, j = 0
        var hashSet = [Character]()
        for c in s {
            if !hashSet.contains(c) {
                j += 1
                hashSet.append(c)
                maxLen = max(maxLen, j - i)
            } else {
                repeat {
                    hashSet.removeFirst()
                    i += 1
                } while hashSet.contains(c)
                j += 1
                hashSet.append(c)
            }
        }
        return maxLen
    }
}
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        i = 0
        j = 0
        hash_set = []
        n = len(s)
        while i < n and j < n:
            c = s[j]
            if c not in hash_set:
                hash_set.append(c)
                j += 1
                max_len = max(max_len, j - i)
            else:
                hash_set.remove(s[i])
                i += 1
        return max_len

复杂度分析

  • 时间复杂度:O(2n)=O(n)

    在最糟糕的情况下,每个字符将别 ij 访问两次。

  • 空间复杂度:O(min(m,n))

    我们需要 O(k) 的空间来检查子字符串中是否有重复字符,其中 k 表示集合的大小。而集合的大小取决于字符串的大小 n 以及字符集/字母的大小 m

优化的滑动窗口

算法

上述滑动窗口的方法最多执行 2n 个步骤。实际上,它可以被进一步优化仅需 n 个步骤。我们可以定义字符到索引的映射,而不是使用集合来判断一个字符是否存在。当我们找到重复的字符时,我们可以立即跳过该窗口。

也就是说,如果 s[j][i,j) 的范围内有与 j' 重复的字符,我们不需要逐渐增加 i 。我们可以直接跳过 [i,j'] 范围内的所有元素,并将 i 变为 j'+1

实现

使用哈希表
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var maxLen = 0, i = 0, j = 0
        var hashMap = [Character:Int]()
        for c in s {
            if let index = hashMap[c] {
                i = max(index, i)
            }
            maxLen = max(maxLen, j - i + 1)
            j += 1
            hashMap[c] = j
        }
        return maxLen
    }
}
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        i = 0
        hash_map = {}
        n = len(s)
        for j in range(n):
            if s[j] in hash_map:
                i = max(hash_map[s[j]], i)
            max_len = max(max_len, j - i + 1)
            hash_map[s[j]] = j + 1
        return max_len
使用字符集

以前的我们都没有对字符串 s 所使用的字符集进行假设。

当我们知道该字符集比较小的时侯,我们可以用一个整数数组作为直接访问表来替换 Map。

常用的表如下所示:

字符集
int[26] 字母 a - z 或者 A - Z
int[128] ASCII 码
int[256] 扩展的 ASCII 码
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var maxLen = 0, i = 0, j = 0
        var index = Array<Int>(repeating: 0, count: 128)
        for c in s {
            if let k = c.asciiValue {
                i = max(index[Int(k)], i)
                maxLen = max(maxLen, j - i + 1)
                j += 1
                index[Int(k)] = j
            }
        }
        return maxLen
    }
}
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        i = 0
        index = [0 for _ in range(128)]
        n = len(s)
        for j in range(n):
            i = max(index[ord(s[j])], i)
            max_len = max(max_len, j - i + 1)
            index[ord(s[j])] = j + 1
        return max_len

复杂度分析

  • 时间复杂度:O(n)

    索引 j 将会迭代 n 次。

  • 空间复杂度(使用哈希表):O(min(m,n))

    我们需要 O(k) 的空间来检查子字符串中是否有重复字符,其中 k 表示集合的大小。而集合的大小取决于字符串的大小 n 以及字符集/字母的大小 m

  • 空间复杂度(使用字符集):O(m)

    m 是字符集的大小。