Given a string, find the length of the **longest substring **without repeating characters.
Examples:
Given"abcabcbb", the answer is"abc", which the length is 3.
Given"bbbbb", the answer is"b", with the length of 1.
Given"pwwkew", the answer is"wke", with the length of 3. Note that the answer must be a substring,"pwke"is a subsequence and not a substring.
Subscribe to see which companies asked this question.
題目描述如上罕拂。
一開(kāi)始的想法就是維護(hù)start，end分別表示substring with non-repeating characters的起始和結(jié)束衷掷。但是如何更新以及在什么時(shí)候更新這兩個(gè)變量蛋济，沒(méi)有弄清楚炮叶。匆忙寫(xiě)了代碼，提交镜悉，自然是wrong answer【衫В看了discuss之后稼锅，仿照java版的答案，寫(xiě)了C++的版本矩距。
代碼如下。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxlen = 0;
map<char,int> dict;
for(int i=0,j=0 ; i<s.size() ; ++i )
{
if( dict.find(s[i])!=dict.end() )
{
//j=max(j,dict[s[i]]+1);
//a case of demo
//why we need a max value
//abcba
if(j<dict[s[i]]+1)
j=dict[s[i]]+1;
}
dict[s[i]]=i;
if( maxlen<i-j+1 )
maxlen = i-j+1;
//maxlen = max(maxlen,i-j+1);
}
return maxlen;
}
};
1.需要注意每次更新j時(shí)陡蝇，都需要將j同dict[s[i]]+1進(jìn)行比較，選擇兩者中的較大數(shù)登夫，如果僅將j更新成dict[s[i]]+1，而沒(méi)有進(jìn)行比較鸦致，就不能處理如abcba的情形戏蔑。
