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.
C Solution 1:
int lengthOfLongestSubstring(char* s) {
int flag[256] = {0};
int res = 0, limit = -1;
int i;
for (i = 0; s[i]; i++) {
if (!flag[s[i]]) {
flag[s[i]] = i + 1;
continue;
}
if (limit >= flag[s[i]] - 1) {
flag[s[i]] = i + 1;
continue;
}
int cur = i - limit - 1;
res = res > cur ? res : cur;
limit = flag[s[i]] - 1;
flag[s[i]] = i + 1;
}
int cur = i - limit - 1;
return res > cur ? res : cur;
}
C Solution 2:
int lengthOfLongestSubstring(char* s) {
char *prepos[256] = {0};
char *l, *r;
int max = 0;
for (l = s, r = s; *r; r++) {
if (prepos[*r] >= l) {
if (r - l > max) max = r - l;
l = prepos[*r] + 1;
}
prepos[*r] = r;
}
if (r - l > max) max = r - l;
return max;
}
C Solution 3:
int lengthOfLongestSubstring(char* s) {
if (!s) return 0;
char *flag[256] = {0}, *l, *r;
int res = 0;
for (l = s, r = s; *r; r++) {
if (flag[*r] >= l) l = flag[*r] + 1;
else if (r - l + 1 > res) res = r - l + 1;
flag[*r] = r;
}
return res;
}
Python Solution 1:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
res, l, ci = 0, 0, {}
for r, c in enumerate(s):
if ci.get(c, -1) >= l: l = ci[c] + 1
else: res = max(res, r - l + 1)
ci[c] = r
return res
Python Solution 2:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s: return 0
start = 0
d = {}
res = 1
for i, c in enumerate(s):
if c in d and d[c] >= start:
res = max(res, i - start)
start = d[c] + 1
d[c] = i
res = max(res, len(s) - start)
return res
Summary:
- C Solution 2 is beautiful. to understand corner case is the key point to write concise code.
近期评论