# 3. Longest Substring Without Repeating Characters

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. Brute force:计算每一个子串，然后判断其是否同时满足最长和无重复的条件，这个方法容易想到但一定会造成超时，因为时间复杂度是立方级的。
2. hash+sliding window:首先，我们假设目前子串存在于{i,j}这个区间内，同时我们用哈希表来记录每一个字母的下标，假如此时下标为j+1的元素和前面的区间中某一个字符相同，即存在于哈希表之中，那么我们应该从下标为j+1的元素继续向后搜索，同时从哈希表中删除下标为i的元素;如果这个新的元素不存在于哈希表中，那么只需让j继续向后移动即可，代码如下:
/*solution1 hash-map+sliding window*/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty())
return 0;
unordered_map<char,int> hash;
int longest,res=0,i=0,j=0,size=s.size();
string tmp;
while(i<size&&j<size){
if(hash.find(s[j])==hash.end()){
hash[s[j++]]=j;
res=max(res,j-i);
}
else
hash.erase(s[i++]);
}
return res;
}
};



/*solution2*/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> mymap(256,-1);
int i,last=0,res=0;
for(i=0;i<s.length();i++) {
if(mymap[s[i]]==-1 || mymap[s[i]]<last)
res = max(res,i-last+1);
else
last = mymap[s[i]]+1;
mymap[s[i]]=i;
}
return res;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017