TypeScript算法-3: 最长无重复子串

TypeScript算法-3. 无重复字符的最长子串

• 理念
  • 程序

思路

针对此类寻找连续子串（而非子序列，因为子序列中的元素不具有连续性）的问题，首先应考虑是否能够借助滑动窗口的方法进行求解。

若依次递增地确定子串的起始位置，则其对应的结束位置也会随之递增。其背后的原因在于：假设我们选取字符串中第 k 个字符作为起始点，并找到以该位置为起点、不含重复字符的最长子串的结束位置为 rk。当我们将起始点调整为第 k+1 个字符时，从 k+1 到 rk 的字符显然不会出现重复的情况。由于此时已排除了原起始点处的字符，因此可以尝试进一步扩展 rk 的范围，直到在右侧遇到重复字符为止。

正是由于上述特性存在，使得我们可以采用「滑动窗口」这一策略来应对此类问题。

代码

    function lengthOfLongestSubstring(s: string): number {
    if (!s.length) return 0;
    if (s.length === 1) return 1;
    let res = 0, l = 0, r = 1;  // [l, r]滑动窗口
    const curCharSet = new Set();
    curCharSet.add(s[l]);
    while