题目:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given"abcabcbb", the answer is"abc", which the length is3.
Given"bbbbb", the answer is"b", with the length of1.
Given"pwwkew", the answer is"wke", with the length of3. Note that the answer must be a substring, >"pwke" is a subsequence and not a substring.题目大意：
给定一个字符串，找到最长子字符串的长度而不重复字符。
例子：
给定"abcabcbb"，答案是"abc"，长度为3
给定"bbbbb"，答案是"b"，长度为1
给定"pwwkew"，答案是"wke"，长度为3.请注意，答案必须是子字符串，"pwke"是子序列而不是子字符串
具体实现
//1：基本的实现方案
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int pos = 0;
int max_len = 0;
string strstr = "";
string max_str = "";
for (int i = 0; i < s.size(); ++i) {
pos = strstr.find(s[i]);
if (pos != -1) {
if (strstr.size() > max_len) {
max_len = strstr.size();
max_str = strstr;
}
strstr = strstr.substr(pos+1, strstr.size());
}
strstr += s[i];
}
if (strstr.size() > max_len) {
max_len = strstr.size();
max_str = strstr;
}
return max_len;
}
};
// 2：牛逼的解决方案
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;
}
