本文旨在深入探讨寻找字符串中最长无重复字符子串问题的解法，重点分析滑动窗口算法的时间复杂度。通过对一种常见实现的剖析，揭示其潜在的 O(n^2) 时间复杂度，并提供优化后的 O(n) 解决方案，该方案利用 Map 数据结构提升效率和可读性。同时，我们还将讨论空间复杂度的影响因素，帮助读者全面理解算法性能。
在字符串处理中，寻找最长无重复字符子串是一个经典问题。常见的解法是使用滑动窗口技术。然而，即使采用了滑动窗口的思想，不同的实现方式也会导致不同的时间复杂度。本文将分析一种常见的滑动窗口实现，指出其潜在的性能瓶颈，并提供一种更优的解决方案。
问题描述
给定一个字符串，找到其中最长的不包含重复字符的子串的长度。
例如：
- 输入 "abcabcbb"，答案是 3，因为最长无重复子串是 "abc"。
- 输入 "bbbbb"，答案是 1，因为最长无重复子串是 "b"。
- 输入 "pwwkew"，答案是 3，因为最长无重复子串是 "wke"。注意，答案必须是子串，"pwke" 是子序列，不是子串。
常见实现的复杂度分析
以下代码展示了一种常见的滑动窗口实现：
var lengthOfLongestSubstring = function(str) {
// Create storage object for caching
let storage = {
longestSubStringLength: 0,
longestSubString: 0,
cache: {
subString: ''
}
};
// Loop through string
for (let i = 0; i < str.length; i++) {
let char = str[i];
if (!storage.cache[char] && storage.cache[char] !== 0) {
// If current letter is not in storage, add it and extend current substring
storage.cache[char] = i;
storage.cache.subString += char;
} else {
// If current letter is already in storage, start a new round
let previousCache = storage.cache;
storage.cache = {
subString: ''
};
if (previousCache[char] + 1 !== i) { // If there are letters in-between
storage.cache.subString = str.substring(previousCache[char] + 1, i);
for (let j = previousCache[char]; j < i; j++) {
storage.cache[str[j]] = j;
}
}
storage.cache[char] = i;
storage.cache.subString += char;
}
// If current substring is the longest, update it in storage
if (storage.cache.subString.length > storage.longestSubStringLength) {
storage.longestSubStringLength = storage.cache.subString.length;
storage.longestSubString = storage.cache.subString;
}
}
return storage.longestSubStringLength;
};这段代码虽然使用了滑动窗口的思想，但其时间复杂度并非 O(n)。主要问题在于内部的 for 循环：
for (let j = previousCache[char]; j < i; j++) {
storage.cache[str[j]] = j;
}当遇到重复字符时，这个循环会遍历之前子串中的一部分字符，更新它们在 storage.cache 中的索引。在最坏的情况下，例如输入 "abcdefghabcdefgh"，这个内部循环会被多次触发，导致时间复杂度上升到 O(n^2)。
具体来说，外层循环遍历字符串的每个字符，复杂度为 O(n)。内层循环的执行次数取决于重复字符之间的距离。在最坏情况下，内层循环的平均执行次数也可能接近 O(n)，因此总的时间复杂度为 O(n * n) = O(n^2)。
优化后的 O(n) 解决方案
为了将时间复杂度降低到 O(n)，可以使用 Map 数据结构来记录字符的索引，并避免内部循环。
const lengthOfLongestSubstring = str => {
let cnt = 0;
let n = str.length;
let answer = 0;
let map = new Map(); // to store the strings and their length
for (let start = 0, end = 0; end < n; end++) { // slide
// move start if the character is already in the map
if (map.has(str[end])) start = Math.max(map.get(str[end]), start);
answer = Math.max(answer, end - start + 1); // longest string
map.set(str[end], end + 1);
cnt++
}
return answer;
}这段代码使用 Map 来存储每个字符最后出现的位置。当遇到重复字符时，直接更新滑动窗口的起始位置 start，而不需要遍历之前的子串。
时间复杂度分析：
- 外层循环遍历字符串的每个字符，复杂度为 O(n)。
- Map 的 has 和 get 操作的平均时间复杂度为 O(1)。
- 因此，总的时间复杂度为 O(n)。
空间复杂度分析：
空间复杂度为 O(min(m, n))，其中 m 是字符集的大小，n 是字符串的长度。Map 最多存储 m 个不同的字符及其索引。在字符集较小的情况下，空间复杂度可以认为是 O(1)。
总结与注意事项
通过使用 Map 数据结构，我们可以将寻找最长无重复字符子串问题的时间复杂度从 O(n^2) 降低到 O(n)。在实际应用中，应根据字符集的大小选择合适的数据结构。如果字符集非常大，可以考虑使用其他数据结构或算法，以避免过高的空间复杂度。
注意事项：
- 理解滑动窗口算法的核心思想。
- 选择合适的数据结构来优化时间复杂度。
- 注意空间复杂度的影响，特别是当字符集较大时。
总而言之，解决算法问题不仅要关注算法的正确性，还要深入分析其时间复杂度和空间复杂度，选择最优的解决方案。
