无重复字符的最长子串

/*
 * 题目：无重复字符的最长子串
 * 要求：输入一个字符串，返回其中最长的无重复字符连续片段的长度。子串必须连续；重复字符出现时只丢弃必要的左侧部分，空串返回 0。两种实现按 JavaScript 字符串下标处理 UTF-16 码元，普通 emoji 不在本题验证范围。
 * 示例：输入 abcabcbb，输出 3，对应 abc；输入 abba，输出 2。
 */
// 方案一
const lengthOfLongestSubstring1 = (str) => {};
console.log(lengthOfLongestSubstring1("")); // 预期：0
console.log(lengthOfLongestSubstring1("abcabcbb")); // 预期：3
console.log(lengthOfLongestSubstring1("abba")); // 预期：2
console.log(lengthOfLongestSubstring1("pwwkew")); // 预期：3


// 方案二
const lengthOfLongestSubstring2 = (str) => {};
console.log(lengthOfLongestSubstring2("")); // 预期：0
console.log(lengthOfLongestSubstring2("abcabcbb")); // 预期：3
console.log(lengthOfLongestSubstring2("abba")); // 预期：2
console.log(lengthOfLongestSubstring2("pwwkew")); // 预期：3

const lengthOfLongestSubstring = (str) => {
  let temp = "";
  let max = 0;

  for (let i = 0; i < str.length; i++) {
    const part = str[i];
    const matchIndex = temp.indexOf(part);

    if (matchIndex === -1) {
      temp += part;
      max = Math.max(max, temp.length);
    } else {
      max = Math.max(max, temp.length);
      temp = temp.slice(matchIndex + 1) + part;
    }
  }

  return max;
};
console.log(lengthOfLongestSubstring("")); // 预期：0
console.log(lengthOfLongestSubstring("abcabcbb")); // 预期：3
console.log(lengthOfLongestSubstring("abba")); // 预期：2
console.log(lengthOfLongestSubstring("pwwkew")); // 预期：3

const lengthOfLongestSubstring = (str) => {
  let map = new Map(); // 字符 → 最新出现的索引

  let max = 0;
  let left = 0; // 窗口左边界（闭区间）

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

    // 关键①：仅当字符存在且索引在窗口内，才移动左边界（处理两个相邻 且 相等的字符）
    // 关键②：>= left 因为可能是第一项
    if (map.has(part) && map.get(part) >= left) {
      left = map.get(part) + 1;
    }

    map.set(part, right); // 更新字符最新索引
    max = Math.max(max, right - left + 1);
  }

  return max;
};
console.log(lengthOfLongestSubstring("")); // 预期：0
console.log(lengthOfLongestSubstring("abcabcbb")); // 预期：3
console.log(lengthOfLongestSubstring("abba")); // 预期：2
console.log(lengthOfLongestSubstring("pwwkew")); // 预期：3