Q3. Longest Substring Without Repeating Characters
直达:https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
Given a string, find the length of thelongest substringwithout 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 asubstring,"pwke"
is asubsequenceand not a substring.
分析
用哈希表存储每个元素的下标(hash[s[i]] = i
)如重复,可用新的下标覆盖旧的下标。遍历字符串,如果哈希表中不存在该字符,
C++代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map <char, int> hash;
int res = 0;
int cur_res = 0;
for (int i = 0; i<s.size(); i++){
if (hash.find(s[i]) == hash.end()){
cur_res += 1;
}else{
cur_res = min((i-hash[s[i]]), (cur_res+1));
}
hash[s[i]] = i;
res = res>cur_res?res:cur_res;
}
return res;
}
};
Last updated
Was this helpful?