【CODE】Longest Substring Without Repeating Characters
3787 ワード
3. Longest Substring Without Repeating Characters
(最長重複しないサブストリング)
Medium
6874410FavoriteShare
Given a string, find the length of the longest substring without repeating characters.
Example 1:
(最長重複しないサブストリング)
Medium
6874410FavoriteShare
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) {
int max=1;
if(s.size()==0) return 0;
for(int i=0;imax) max=len;
str+=s[j];
}
else{
if(len>max) max=len;
j=s.size();
}
}
}
return max;
}
};
- Runtime: 84 ms, faster than 15.11% of C++ online submissions for Longest Substring Without Repeating Characters.
- Memory Usage: 21.5 MB, less than 11.94% of C++ online submissions for Longest Substring Without Repeating Characters.
- Next challenges:
- Longest Substring with At Most Two Distinct Characters
- Longest Substring with At Most K Distinct Characters
- Subarrays with K Different Integers
- dp[i][j]: i j , 。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max=1;
if(s.size()==0) return 0;
string str=s.substr(0,1);
int left=0,right=1;
while(leftmax) max=right-left;
}else{
if(right-left>max) max=right-left;
left=f+left+1;right++;
str=s.substr(left,right-left);
}
}
return max;
}
};
- Runtime: 16 ms, faster than 71.44% of C++ online submissions for Longest Substring Without Repeating Characters.
- Memory Usage: 13.9 MB, less than 25.87% of C++ online submissions for Longest Substring Without Repeating Characters.