# Question:

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.```

# Solution:

Java 代码如下：

```public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int length = s.length();
int left = 0, right = 0;
HashSet<Character> hashSet = new HashSet<>();
while(left < length && right < length){
if (hashSet.contains(s.charAt(right))){
hashSet.remove(s.charAt(left++));
}else{
maxLength = Math.max(maxLength, right - left);
}
}
return maxLength;
}```

```#include <hash_set>

using namespace stdext;

class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 统计最大长度
int maxLength = 0;
// 原字符串长度
int len = s.length();
// 设定左右边界
int left = 0, right = 0;
// 记录已出现字符的 Hash Set
hash_set<char> set;

while(left < len && right < len) {
// 查找右边界的元素是否在 Hash Set 中出现
// 如果找到，则左边界右移
if(set.find(s[right]) != set.end() ) {
set.erase(set.find(s[right++]));
left++;
}
// 如果没找到，则将右边界所在字符添加进入 Hash Set，并更新最大长度
else {
set.insert(s[right++]);
maxLength = maxLength > (right - left) ? maxLength : (right - left);
}
}

return maxLength;
}
};```

C++ 代码如下（已通过 LeetCode 检验）：

```class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 统计最大长度
int maxLength = 0;
// 原字符串长度
int len = s.length();
// 设定左右边界
int left = 0, right = 0;
// 记录已出现字符以及最右位置的 map
unordered_map<char, int> map;

for(; right < len; ++right) {
// 查找右边界的元素是否在 Hash Set 中出现
// 如果找到，则左边界右移
if(map.find(s[right]) != map.end() ) {
left = map.find(s[right])->second + 1 > left ? map.find(s[right])->second + 1 : left ;
}

// 比较并更新最大长度
maxLength = maxLength > (right - left + 1) ? maxLength : (right - left + 1);
// 更新 Key 值
map[s[right]] = right;
}

return maxLength;
}
};```

0 条评论