給定一個字符串?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?由英文字母、數字、符號和空格組成

題解

首先是我自己的思路，因為比較直接所以比較暴力

遍歷字符串的每個字符，按照當前無重復字符的字串的長度提取子串，在字串中尋找是否有相同的字符，如果有相同的字符，更新子串的起始字符為相同字符的后面一個字符，同時更新當前字串的長度

這里尋找相同字符的位置比較講究，首先找出相同字符在子串的位置，再加上字串在字符串中的位置，之所以用rfind倒著查找是避免存在多個相同字串返回第一個字串的結果，用rfind加上i的位置可以返回正確位置的子串的位置

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s=="")return 0;int longest=1,begin=0,longer=1;string son;for(int i=1;i<s.size();i++){son=s.substr(begin,longer);int newBegin=son.find(s[i]);if(newBegin!=string::npos){newBegin=s.rfind(son,i-1)+newBegin;longer=i-newBegin;begin=newBegin+1;}else{longer++;longest=longest<longer?longer:longest;}}return longest;}
};

下面這個是更加簡潔和優化的寫法，思路還是一樣的

class Solution {
public:int lengthOfLongestSubstring(string s) {int longest=0,begin=0,end=0;while(end<s.size()){for(int i=begin;i<end;i++){ //子串重復判斷if(s[i]==s[end]){begin=i+1; //更新子串起始位置break;}}longest=max(longest,end-begin+1);end++;}return longest;}
};

?