# 3. Longest Substring Without Repeating Characters

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

Example 1:

**Input:** s = "abcabcbb"
**Output:** 3
**Explanation:** The answer is "abc", with the length of 3.

Example 2:

**Input:** s = "bbbbb"
**Output:** 1
**Explanation:** The answer is "b", with the length of 1.

Example 3:

**Input:** s = "pwwkew"
**Output:** 3
**Explanation:** The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

C++ 解法一：

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = -1, n = s.size();
unordered_map<int, int> m;
for (int i = 0; i < n; ++i) {
if (m.count(s[i]) && m[s[i]] > left) {
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};

C++ 解法二：

class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> m(128, -1);
int res = 0, left = -1;
for (int i = 0; i < s.size(); ++i) {
left = max(left, m[s[i]]);
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};

Java 解法二：

public class Solution {
public int lengthOfLongestSubstring(String s) {
int[] m = new int[256];
Arrays.fill(m, -1);
int res = 0, left = -1;
for (int i = 0; i < s.length(); ++i) {
left = Math.max(left, m[s.charAt(i)]);
m[s.charAt(i)] = i;
res = Math.max(res, i - left);
}
return res;
}
}

C++ 解法三：

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = 0, i = 0, n = s.size();
unordered_set<char> t;
while (i < n) {
if (!t.count(s[i])) {
t.insert(s[i++]);
res = max(res, (int)t.size());
} else {
t.erase(s[left++]);
}
}
return res;
}
};

Java 解法三：

public class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0, left = 0, right = 0;
HashSet<Character> t = new HashSet<Character>();
while (right < s.length()) {
if (!t.contains(s.charAt(right))) {
res = Math.max(res, t.size());
} else {
t.remove(s.charAt(left++));
}
}
return res;
}
}

Github 同步地址：

https://github.com/grandyang/leetcode/issues/3

Longest Substring with At Most Two Distinct Characters

Longest Substring with At Most K Distinct Characters

Subarrays with K Different Integers

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

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1737/C++-code-in-9-lines.

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1812/Share-my-Java-solution-using-HashSet

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1729/11-line-simple-Java-solution-O(n)-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation