03. 无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

题解

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int m = 0, n = 0, l = 0;
        for (n = 0; n < s.size(); n++) {
            auto pos = s.substr(m, n - m).find(s[n]);
            if (pos == std::string::npos) {
                continue;
            } else {
                l = max(l, (n - m));
                m += (pos + 1);
            }
        }
        return max(l, (n - m));
    }
};

总结

1. 解决关键词：滑动窗口，双指针
2. 右侧边界 n 滑动，从当前窗口 substr(m, n - m) 中查找 s[n],如果找到，则将左侧边界 m 滑动至 pos + 1，不断重复
3. 对 std::string::substr 使用 find 方法时，需要额外加上 substr 在原始字符串的起始位置
4. substr 和 find 方法并非最优解，使用表存储字符出现的位置，查找时间复杂度为 O(n)。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int idx[128];
        memset(idx, -1, sizeof(idx));
        int m = 0, n = 0, l = 0;
        for(n = 0; n < s.size(); n++) {
            // idx[s[n]] + 1 当前字符上一次出现的索引值 + 1
            // 确保 m 左侧边界已经越过重复字符 s[n]，始终保持滑动窗口为 [m,n] 的闭区间
            // 即确保子串 s[m,n] 中没有重复字符
            m = max(m, idx[s[n]] + 1);
            // 因此子串长度为 n - m + 1
            l = max(l, n - m + 1);
            // 记录当前字符 s[n] 的索引值
            idx[s[n]] = n;
        }
        return l;
    }
};