无重复字符的最长子串

题目要求

给定一个字符串 s，要求编写一个算法来找出这个字符串中最长的不包含重复字符的子串，并返回这个最长子串的长度。

解题思路

解决这个问题的一个有效方法是使用滑动窗口算法。滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中的一个子列表，并且可以在一定条件下向左或向右滑动。

具体到这个问题，我们可以定义一个窗口，它可以在字符串上从左向右滑动，窗口内是一个不包含重复字符的子串。我们的目标是找到最长的这样的窗口。

以下是解题步骤：

初始化两个指针，分别表示窗口的左边界和右边界，初始化为字符串的起始位置。
使用一个数据结构（如哈希表）来存储窗口内的字符及其索引，以便快速判断字符是否重复以及获取重复字符的索引。
移动右边界，扩展窗口，将新字符加入到哈希表中。如果字符不在哈希表中，更新当前无重复字符子串的长度，并与已知的最长长度进行比较，如果更长，则更新最长长度。
如果遇到哈希表中已存在的字符，说明当前子串中已经有了重复字符，此时需要移动左边界来缩小窗口。移动左边界到重复字符的下一个位置，并在哈希表中更新相关字符的索引。
重复步骤 3 和 4，直到右边界到达字符串的末尾。
返回记录的最长长度作为答案。

这个算法的关键在于，当我们遇到重复字符时，我们可以跳过窗口中所有重复字符之前的部分，因为这些部分不可能是最长的无重复字符子串。这样，我们就不需要对这些字符再次进行检查，从而提高了算法的效率。

Golang 版本

func lengthOfLongestSubstring(s string) int {
    charIndexMap := make(map[byte]int)
    maxLength := 0
    start := 0 // 窗口开始位置

    for i := 0; i < len(s); i++ {
        if index, ok := charIndexMap[s[i]]; ok && index >= start {
            // 如果字符s[i]在窗口中已存在，移动窗口的开始位置
            start = index + 1
        }
        // 更新字符索引
        charIndexMap[s[i]] = i
        // 计算当前窗口长度，并更新最大长度
        if i-start+1 > maxLength {
            maxLength = i - start + 1
        }
    }

    return maxLength
}

这段代码实现了上述的滑动窗口算法。它使用一个哈希表charIndexMap来存储字符和它们最新的索引。变量start表示当前窗口的开始位置，maxLength用于记录遇到的最长子串的长度。遍历字符串s时，如果当前字符在哈希表中存在且索引大于等于start，则更新start到重复字符的下一个位置。每次迭代都会更新哈希表，并可能更新maxLength。最终返回maxLength作为结果。

C++版本

#include <string>
#include <unordered_map>
#include <algorithm>

int lengthOfLongestSubstring(std::string s) {
    std::unordered_map<char, int> charIndexMap;
    int maxLength = 0;
    int start = 0; // 窗口开始位置

    for (int i = 0; i < s.length(); ++i) {
        auto found = charIndexMap.find(s[i]);
        if (found != charIndexMap.end() && found->second >= start) {
            // 如果字符s[i]在窗口中已存在，移动窗口的开始位置
            start = found->second + 1;
        }
        // 更新字符索引
        charIndexMap[s[i]] = i;
        // 计算当前窗口长度，并更新最大长度
        maxLength = std::max(maxLength, i - start + 1);
    }

    return maxLength;
}

这段 C++代码实现了与 Golang 版本相同的滑动窗口算法。它使用std::unordered_map来存储字符和它们最新的索引。变量start表示当前窗口的开始位置，maxLength用于记录遇到的最长子串的长度。在遍历字符串s时，如果当前字符在哈希表中存在且索引大于等于start，则更新start到重复字符的下一个位置。每次迭代都会更新哈希表，并可能更新maxLength。最终返回maxLength作为结果。

Python 版本

def length_of_longest_substring(s: str) -> int:
    char_index_map = {}
    max_length = 0
    start = 0  # 窗口开始位置

    for i, char in enumerate(s):
        if char in char_index_map and char_index_map[char] >= start:
            start = char_index_map[char] + 1
        char_index_map[char] = i
        max_length = max(max_length, i - start + 1)

    return max_length

这段 Python 代码实现了前面描述的滑动窗口算法。它使用一个字典char_index_map来存储字符和它们最新的索引。变量start表示当前窗口的开始位置，max_length用于记录遇到的最长子串的长度。在遍历字符串s时，如果当前字符在字典中存在且索引大于等于start，则更新start到重复字符的下一个位置。每次迭代都会更新字典，并可能更新max_length。最终返回max_length作为结果。

Java 版本

import java.util.HashMap;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charIndexMap = new HashMap<>();
        int maxLength = 0;
        int start = 0; // 窗口开始位置

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (charIndexMap.containsKey(ch) && charIndexMap.get(ch) >= start) {
                start = charIndexMap.get(ch) + 1;
            }
            charIndexMap.put(ch, i);
            maxLength = Math.max(maxLength, i - start + 1);
        }

        return maxLength;
    }
}

这段 Java 代码实现了滑动窗口算法。它使用一个HashMap来存储字符和它们最新的索引。变量start表示当前窗口的开始位置，maxLength用于记录遇到的最长子串的长度。在遍历字符串s时，如果当前字符在哈希表中存在且索引大于等于start，则更新start到重复字符的下一个位置。每次迭代都会更新哈希表，并可能更新maxLength。最终返回maxLength作为结果。

Rust 版本

#![allow(unused)]
fn main() {
use std::collections::HashMap;

pub fn length_of_longest_substring(s: String) -> i32 {
    let mut char_index_map: HashMap<char, usize> = HashMap::new();
    let mut max_length = 0;
    let mut start = 0; // 窗口开始位置

    for (i, c) in s.chars().enumerate() {
        if let Some(&index) = char_index_map.get(&c) {
            if index >= start {
                start = index + 1;
            }
        }
        char_index_map.insert(c, i);
        max_length = max_length.max(i - start + 1);
    }

    max_length as i32
}
}

这段 Rust 代码实现了滑动窗口算法。它使用一个HashMap来存储字符和它们最新的索引。变量start表示当前窗口的开始位置，max_length用于记录遇到的最长子串的长度。在遍历字符串s时，如果当前字符在哈希表中存在且索引大于等于start，则更新start到重复字符的下一个位置。每次迭代都会更新哈希表，并可能更新max_length。最终返回max_length作为结果。

总结

上述代码片段展示了如何在不同编程语言中实现寻找字符串中最长不含重复字符子串的长度的算法。核心思想是使用滑动窗口和哈希表（或字典）来跟踪字符最后出现的位置。算法的步骤如下：

初始化一个哈希表来存储字符和它们在字符串中的索引。
使用两个指针表示滑动窗口的开始和结束位置，开始时都指向字符串的起始位置。
遍历字符串，对于每个字符：
- 如果字符已经在哈希表中，并且其索引大于等于当前窗口的开始位置，更新窗口的开始位置到该重复字符的下一个位置。
- 将当前字符及其索引放入哈希表中。
- 更新最长子串的长度。
遍历完成后，返回记录的最长长度作为答案。

这种方法的时间复杂度为 O(n)，其中 n 是字符串的长度，因为每个字符只被访问一次。空间复杂度为 O(min(m, n))，其中 m 是字符集的大小，这是因为哈希表最多存储 m 个键值对。对于大多数情况，m 远小于 n，因此可以认为空间复杂度接近于 O(1)。

不同编程语言的实现细节略有不同，但算法的核心逻辑是一致的。例如，Rust 使用HashMap，C++使用std::unordered_map，Python 使用字典，Java 使用HashMap，而 Go 使用内置的 map 类型。尽管语法不同，但它们都提供了快速查找和更新键值对的功能，这对于算法的实现至关重要。

hot-100