JZ48 最长不含重复字符的子字符串

发表于 更新于 分类于 本文字数： 424 阅读时长 ≈ 2 分钟

JZ48 最长不含重复字符的子字符串

描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

数据范围: s.length≤40000 $

示例1

1
2
3
输入："abcabcbb"
返回值：3
说明：因为无重复字符的最长子串是"abc"，所以其长度为 3。

示例2

1
2
3
输入："bbbbb"
返回值：1
说明：因为无重复字符的最长子串是"b"，所以其长度为 1。

示例3

1
2
3
输入："pwwkew"
返回值：3
说明：因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

题解

还是学艺不精啊，自己做了半天，从集合改成$map$，然后还是少了一个双指针来记录窗口。以$dp[i]$表示以$s[i]$为结尾的最长无重复字串长度，以$left$表示最长字串的起点，每个字符上次出现的位置用$map[s[i]]记录$。
$$
当s[i]不在窗口内时，dp[i] = dp[i-1] + 1,left = left\
否则，dp[i]=i-map[s[i]],left = map[s[i]]+1\
ans = mas(ans,dp[i])
$$
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <map>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> lastIndex;  // 记录每个字符上一次出现的位置
        int ans = 0;
        int left = 0;               // 当前无重复子串的起点

        for(int i = 0; i < s.size(); i++) {
            if(lastIndex.find(s[i]) != lastIndex.end() && lastIndex[s[i]] >= left) {
                // 当前字符重复，并且上一次出现的位置在窗口内
                left = lastIndex[s[i]] + 1;  // 移动窗口左端
            }
            lastIndex[s[i]] = i;      // 更新字符位置
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};