3. Longest Substring Without Repeating Characters
难度:Medium
刷题内容
原题连接
- 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.
解题方案
思路 1 **- 时间复杂度: O(NlgN)*- 空间复杂度: O(N)***
用 map储存 key为字符，value 为这个字符的位置，我们可以维护一个子字符串(无重复字符)，记录它的起始位置，遍历 string s 当无法在map中找到字符或者小于子字符串的起始位置，就是没有在这个字符串中出现，反之则字符重复，不过 map查找为 O(lgn)，因此总的时间复杂度为O(NlgN)
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;
}
};
思路 2 **- 时间复杂度: O(NlgN)*- 空间复杂度: O(1)***
这个思路和上面差不多，用到了一个小窍门，因为储存的是字符，char为8位，因此能储存的最大数为256，这样空间复杂度就为O(1)
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;
}
};
