无重复字符的最长子串

找到字符串中不含有重复字符的最长子串长度有多种解法。下面介绍两种常见解法：滑动窗口法（推荐）和动态规划法。

方法一：滑动窗口法

滑动窗口法是一种常见且高效的方法，可以在线性时间内找到答案。使用两个指针表示滑动窗口的左右边界，并利用哈希表记录字符出现的位置。

代码：

function lengthOfLongestSubstring(s) {
    const n = s.length;
    const map = new Map();
    let left = 0, maxLength = 0;

    for (let right = 0; right < n; right++) {
        if (map.has(s[right])) {
            left = Math.max(map.get(s[right]) + 1, left);
        }
        map.set(s[right], right);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

解释：

1. 初始化：

   • left 和 right 分别表示滑动窗口的左边界和右边界，left 初始化为 0。
   • map 是一个哈希表，用于记录字符及其最新出现的位置。
   • maxLength 记录不含重复字符的最长子串的长度，初始化为 0。

2. 遍历字符串：

   • 对于每个字符 s[right]，如果该字符已经存在于 map 中并且其位置在 left 的右边或等于 left，则说明存在重复字符，需要更新 left，跳过重复字符。
   • 使用 map.set(s[right], right) 更新字符 s[right] 的位置。
   • 计算当前窗口的长度 right - left + 1，更新 maxLength 为其和当前 maxLength 中的较大值。

3. 返回结果：

   • 最后返回 maxLength，即为最长不含重复字符的子串长度。

时间复杂度：O(n)，其中 n 是字符串长度。

空间复杂度：O(min(n, m))，其中 m 是字符集大小。

方法二：动态规划法

动态规划法通过构建一个数组来记录以每个字符结尾的最长无重复子串的长度。

代码：

function lengthOfLongestSubstring(s) {
    const n = s.length;
    if (n === 0) return 0;

    const dp = Array(n).fill(0);
    const map = new Map();
    dp[0] = 1;
    map.set(s[0], 0);
    let maxLength = 1;

    for (let i = 1; i < n; i++) {
        if (map.has(s[i])) {
            const prevIndex = map.get(s[i]);
            dp[i] = Math.min(dp[i - 1] + 1, i - prevIndex);
        } else {
            dp[i] = dp[i - 1] + 1;
        }
        map.set(s[i], i);
        maxLength = Math.max(maxLength, dp[i]);
    }

    return maxLength;
}

解释：

1. 初始化：

   • dp 数组记录以每个字符结尾的最长无重复子串的长度。
   • map 哈希表记录字符出现的位置。
   • 初始化 dp[0] = 1，因为第一个字符单独是一个无重复子串。
   • 初始化 maxLength = 1。

2. 遍历字符串：

   • 对于每个字符 s[i]，如果该字符已经存在于 map 中，则获取其上一次出现的索引 prevIndex。
   • dp[i] 等于 dp[i - 1] + 1 和 i - prevIndex 中的较小值。
   • 如果字符未出现，则 dp[i] = dp[i - 1] + 1。
   • 更新 map 中字符的位置，并更新 maxLength。

3. 返回结果：

   • 最后返回 maxLength。

时间复杂度：O(n)，其中 n 是字符串长度。

空间复杂度：O(n)，因为使用了 dp 数组。

测试用例

// 测试用例1
console.log(lengthOfLongestSubstring("abcabcbb")); // 输出：3，最长子串是 "abc"

// 测试用例2
console.log(lengthOfLongestSubstring("bbbbb")); // 输出：1，最长子串是 "b"

// 测试用例3
console.log(lengthOfLongestSubstring("pwwkew")); // 输出：3，最长子串是 "wke"

// 测试用例4
console.log(lengthOfLongestSubstring("")); // 输出：0，没有子串

// 测试用例5
console.log(lengthOfLongestSubstring("aab")); // 输出：2，最长子串是 "ab"

// 测试用例6
console.log(lengthOfLongestSubstring("dvdf")); // 输出：3，最长子串是 "vdf"

// 测试用例7
console.log(lengthOfLongestSubstring("anviaj")); // 输出：5，最长子串是 "nviaj"

总结

• 滑动窗口法适用于一般情况，代码简洁，时间和空间复杂度均较优。
• 动态规划法适用于理解子问题，但空间复杂度稍高。

根据实际需求选择合适的方法。