Leetcodes Solution 3 Longest Substring Without Repeating Characters

zhuanlan.zhihu.com

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.

思路1

用dict來存儲字元和它出現的索引。start表示目前不相同的子字元串的開頭索引。

用i-start得到所有不相同的子字元串的長度，在比較求出最大的

class Solution{public: int lengthOfLongestSubstring(string s){ vector<int> dict(256, -1); int maxLen = 0, start = -1; for(int i = 0; i != s.length(); i++){ if(dict[s[i]] > start) start = dict[s[i]]; dict[s[i]] = i; maxLen = max(maxLen, i - start); } return maxLen; }};

推薦閱讀：