3. Longest Substring Without Repeating Characters
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.
題解:
輸入一個字符串,求這個字符串中窑邦,不包括重復(fù)元素的最大的子串的長度累驮;
例如對于輸入:"zffcool"
子串為:
"z", "zf", "zff", "zffc", "zffco", "zffcoo","zffcool"帝嗡;
"f", "ff", "ffc", "ffco", "ffcoo","ffcool"框舔;
"f", "fc", "fco", "fcoo","fcool"褐耳;
"c", "co", "coo","cool"泞辐;
"o", "oo","ool"煤辨;
"o", "ol";
"l"诀拭;
則加粗的為不包含重復(fù)字符的子串迁筛;
最長的子串為fco,長度為3耕挨;輸出3细卧;
分析:
兩個指針,begin 指向子串的頭筒占,i 向后滑動贪庙;
當滑到字符曾出現(xiàn)過時,判斷重復(fù)的字符是否在子串中翰苫,在的話更新 begin止邮,讓它指向重復(fù)字符的下一個字符,同時更新重復(fù)字符的位置奏窑;否則导披,在 begin 的前面,說明子串中沒有與當前字符重復(fù)的字符埃唯,直接更新該重復(fù)字符(key)對應(yīng)的當前位置(value)即可撩匕;最后輸出最大的子串長度;
My Solution(C/C++)
#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.length() == 0) {
return 0;
}
map<char, int> hash_map;
vector<int> result;
int count = 0;
int begin = 0;
for (int i = 0; i < s.length(); i++) {
if (hash_map.find(s[i]) == hash_map.end()) {
hash_map.insert(map<char, int>::value_type(s[i], i));
count += 1;
result.push_back(count);
}
else {
if (begin > hash_map[s[i]]) {
count += 1;
}
else {
count = count - (hash_map[s[i]] + 1 - begin) + 1;
begin = hash_map[s[i]] + 1;
}
hash_map[s[i]] = i;
result.push_back(count);
}
}
return *max_element(result.begin(), result.end());
}
};
int main() {
Solution s;
printf("\"abcabcbb\":%d\n", s.lengthOfLongestSubstring("abcabcbb"));
printf("\"bbbbb\":%d\n", s.lengthOfLongestSubstring("bbbbb"));
printf("\"pwwkew\":%d\n", s.lengthOfLongestSubstring("pwwkew"));
printf("\"\":%d\n", s.lengthOfLongestSubstring(""));
printf("\"nfpdmpi\":%d\n", s.lengthOfLongestSubstring("nfpdmpi"));
printf("\"nffdmpn\":%d\n", s.lengthOfLongestSubstring("nffdmpn"));
printf("\"aabaab!bb\":%d", s.lengthOfLongestSubstring("aabaab!bb"));
return 0;
}
結(jié)果
"abcabcbb":3
"bbbbb":1
"pwwkew":3
"":0
"nfpdmpi":5
"nffdmpn":5
"aabaab!bb":3
My Solution1:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
count, ss = [0], ''
for i in range(len(s)):
if s[i] in ss:
ss = ss[ss.index(s[i])+1: ] + s[i]
count.append(len(ss))
else:
ss += s[i]
if len(ss) > 0:
count.append(len(ss))
return max(count)
My Solution2:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if s == '':
return 0
begin, long_s, result = 0, '', 0
for end in range(len(s)):
if long_s.find(s[end]) == -1:
long_s += s[end]
if result < len(long_s):
result = len(long_s)
else:
begin = long_s.find(s[end]) + 1
long_s = long_s[begin: ] + s[end]
return result
Reference (轉(zhuǎn)):
class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}
for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i
return maxLength