博客

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

示例 1:

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

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

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

看代码：

#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;

//无重复的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set <char> sta; //这个效率比set高
        int maxlen = 0;
        int pr = 0;
        
        for(int i = 0; i < s.length(); i++)
        {
            //sta.count(s[pr]) 判断s[pr]是否在sta中
            pr = i;
            while(pr < s.length() && sta.count(s[pr])==0)
            {
                sta.insert(s[pr++]);
            }
            
            maxlen = sta.size() > maxlen? sta.size():maxlen;

            if(pr < s.length())
            {
                sta.erase(s[i]); 
            }
            else
            	break;
        }

		//遍历
		//for(auto it=sta.begin();it!=sta.end();it++){
		//	cout << *it << endl;
		//}
		
        return maxlen;
    }
};


int main(){
	string str = "bbbbb";
	Solution so;
	int n = so.lengthOfLongestSubstring(str);
	cout << n << endl;
	return 0;
}

算法思路：从头开始遍历字符串，然后存到set里面，每次遍历时判断该字符是否在set中，如果不在就加入set，如果在求出当前set长度和上一个长度对比取最大值，清空set，然后i++，从第二个字符开始遍历，知道遇到重复的字符。

参考地址：

https://blog.csdn.net/yangzijiangtou/article/details/107074999