求字符串中最长无重复子序列

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 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]); }elsebreak;}//遍历//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

总结

以上是生活随笔为你收集整理的求字符串中最长无重复子序列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。