# 3. Longest Substring Without Repeating Characters

## 刷题内容

• https://leetcode.com/problems/longest-substring-without-repeating-characters


Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.


## 解题方案

class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<int,int> m;
int beg = 0,length = s.length(),ll = 0,ans = 0;
for(int i = 0;i < length;++i)
{
if(m.find(s[i]) == m.end() || m[s[i]] < beg)
ll++;
else
{
int pos = m[s[i]];
ans = max(ll,ans);
ll = ll - (pos - beg);
beg = pos + 1;
}
m[s[i]] = i;
}
ans = max(ans,ll);
return ans;
}
};


class Solution {
public:
int lengthOfLongestSubstring(string s) {
int m[256];
for(int i = 0;i < 256;++i)
m[i] = -1;
int beg = 0,length = s.length(),ll = 0,ans = 0;
for(int i = 0;i < length;++i)
{
if(m[s[i]] < beg)
ll++;
else
{
int pos = m[s[i]];
ans = max(ll,ans);
ll = ll - (pos - beg);
beg = pos + 1;
}
m[s[i]] = i;
}
ans = max(ans,ll);
return ans;
}
};


apachecn/AiLearning