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

题目描述

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

示例 1:

输入: "abcabcbb"
输出: 3 

解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1

解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3

解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

分析

使用hash表记录字符上一次出现的位置
不重复字符的最长子串的长度为i - begin
初始：
begin = 0
max = max(maxLen, i - begin)
str = "abcabcbb"

i的位置	当前字符	begin	hash	maxLen
0	a	0	{a:0}	0
1	b	0	{a:0,b:1}	0
2	c	0	{a:0,b:1,c:2}	0
3	a	1	{a:1,b:1,c:2}	3
4	b	2	{a:1,b:4,c:2}	3
5	c	3	{a:1,b:4,c:5}	3
6	b	3	{a:1,b:6,c:5}	3
7	b	3	{a:1,b:7,c:5}	3

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        vector<int> m(128, -1);
        int maxLen = 0;
        int begin = 0;
        for(int i = 0; i < n; i++) {
            char c = s[i];
            int pos = m[c];
            if(pos >= begin) {
                maxLen = max(maxLen, i - begin);
                begin = pos + 1;
            } 
            m[c] = i;
        }
        maxLen = max(maxLen, n - begin); //最后一次
        return maxLen;
    }
};

题目链接

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/