# [leetcode] Longest Substring Without Repeating Characters

### Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

tags: hash table, string, two pointers

9/21/2015 update

```//two pointers algorithm, o(n)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> map;
int i, j;
int ans = 0;
i = j = 0;
while(j < s.size()){
if(map.find(s[j]) != map.end()){
//appeared before
map.erase(s[i]);
i++;
}
else{
//not appeared before
map[s[j]] = 1;
ans = max(ans, j - i + 1);
j++;
}
}
return ans;
}
};```

hashtable的key为字符，value为一个包含该字符出现位置的数组，这样可以不用find函数，而是通过查哈希表来实现find的操作。

```//本题中，一个利用hashtable的范例，代替版本一中的string的find函数。
//只是思路，未经编译验证
unordered_map<char, set<int >index> m;
int find(char c, int pos){
if(m.find(c) == m.end()){
return -1;
}
else{
return *m[c].lower_bound();
}
}
```

```class Solution {
public:
int lengthOfLongestSubstring(string s) {
int start = 0;
int maxLength = 0;
for(int i = 0; i < s.size(); i++){
int pos = s.find(s[i], start);
if(pos != string::npos && pos < i){//repeat in substring
start = pos + 1;
}
else{
if(i - start + 1 > maxLength){
maxLength = i - start + 1;
}
}
}
return maxLength;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.