字符串最长的不重复子串

问题

给定一个字符串，找出其中最长的不含有重复字符的子串的长度。例如，字符串 “abcabcbb” 的最长不重复子串是 “abc”，长度为 3；字符串 “bbbbb” 的最长不重复子串是 “b”，长度为 1。

解答

/**
 * 查找字符串中最长的不重复子串
 * @param {string} str - 输入字符串
 * @return {string} - 返回最长不重复子串
 */
function longestUniqueSubstring(str) {
  if (!str || str.length === 0) {
    return '';
  }

  let maxLength = 0; // 最长子串的长度
  let maxStart = 0; // 最长子串的起始位置
  let left = 0; // 滑动窗口左指针
  const charMap = new Map(); // 存储字符及其最新位置

  for (let right = 0; right < str.length; right++) {
    const char = str[right];

    // 如果字符已存在且在当前窗口内，移动左指针
    if (charMap.has(char) && charMap.get(char) >= left) {
      left = charMap.get(char) + 1;
    }

    // 更新字符的最新位置
    charMap.set(char, right);

    // 更新最长子串信息
    const currentLength = right - left + 1;
    if (currentLength > maxLength) {
      maxLength = currentLength;
      maxStart = left;
    }
  }

  return str.substring(maxStart, maxStart + maxLength);
}

/**
 * 只返回最长不重复子串的长度
 * @param {string} str - 输入字符串
 * @return {number} - 返回最长不重复子串的长度
 */
function longestUniqueSubstringLength(str) {
  if (!str || str.length === 0) {
    return 0;
  }

  let maxLength = 0;
  let left = 0;
  const charMap = new Map();

  for (let right = 0; right < str.length; right++) {
    const char = str[right];

    if (charMap.has(char) && charMap.get(char) >= left) {
      left = charMap.get(char) + 1;
    }

    charMap.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

使用示例

// 示例1：基本使用
console.log(longestUniqueSubstring('abcabcbb')); // 输出: "abc"
console.log(longestUniqueSubstringLength('abcabcbb')); // 输出: 3

// 示例2：全部重复字符
console.log(longestUniqueSubstring('bbbbb')); // 输出: "b"
console.log(longestUniqueSubstringLength('bbbbb')); // 输出: 1

// 示例3：全部不重复
console.log(longestUniqueSubstring('abcdef')); // 输出: "abcdef"
console.log(longestUniqueSubstringLength('abcdef')); // 输出: 6

// 示例4：包含空格和特殊字符
console.log(longestUniqueSubstring('pwwkew')); // 输出: "wke"
console.log(longestUniqueSubstringLength('pwwkew')); // 输出: 3

// 示例5：空字符串
console.log(longestUniqueSubstring('')); // 输出: ""
console.log(longestUniqueSubstringLength('')); // 输出: 0

// 示例6：中文字符
console.log(longestUniqueSubstring('我爱编程编程')); // 输出: "我爱编程"
console.log(longestUniqueSubstringLength('我爱编程编程')); // 输出: 4

关键点

• 滑动窗口算法：使用左右两个指针维护一个动态窗口，窗口内始终保持无重复字符

• 哈希表优化：使用 Map 存储每个字符最后出现的位置，实现 O(1) 时间复杂度的查找

• 左指针移动策略：当遇到重复字符时，将左指针移动到重复字符上次出现位置的下一位

• 边界条件判断：需要确保重复字符在当前窗口内（charMap.get(char) >= left），避免左指针回退

• 时间复杂度：O(n)，其中 n 是字符串长度，每个字符最多被访问两次

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