16 Nov 2016 | LeetCode
Given a string, find the length of the longest substring without repeating characters.
给定一个字符串，找到最长的没有重复的字符串。
Given "abcabcbb", the answer is "abc", wich 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.
这几天都没有更新，真心不是在下太懒…是太蠢，这道题目我前前后后想了好几天，各种error，AC不过。最后无奈求助许奕大大，许奕大大大手一挥，过了。这是一个动态规划问题，之前在下采用蠢办法穷举所有的情况，主要存在的逻辑问题是没有考虑一个字符子串中包含另一段符合条件的子串。
此处移植了一下许奕大大的代码。
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
length=0
left=0
begin=0
#s=raw_input("input:")
for i,val in enumerate(s):
flag=True
for j,val2 in enumerate(s[left:i]):
if val==val2:
left=left+j+1
flag=False
break
if flag:
if begin==left:
length+=1
else:
t=i-left+1
if t>length:
begin=left
length=t
print length
许奕大大说动态规划的优势是不重复计算信息。
假设Si为字符串S前i个字符组成的子串，Ti表示所求最长子串，Li表示Ti的长度，S[i]表示Si最后一个字符。在已知Ti的情况下，T(i+1)要么是Ti要么是以S[i+1]结尾的子串。假设Qi是以S[i+1]结尾的最长不重复子串，因为T1=Q0=S1,所以只要让i不断增加，把Qi的长度和Li做比较即可。
此处遍历S，遍历Q(i-1)，如果找到与S[i]相同的字符，则将左边界右移到新找到的字符后，跳出循环。如果没有找到，并且上一次遍历也没找到，即T(i+1)=Qi，则让返回的长度加1,若上一次找到了，则要判断T(i+1)等于Ti还是Qi，比较Qi的长度和返回子串Ti的长度，让返回长度Li等于较大的那个，继续遍历。
以下是许奕大大的cpp代码。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
size_t beg=0,len=0,mid=0;
set<char> cur;
bool flag=true;
for(size_t i=0,j=s.size();i<j;++i) {
char c=s[i];
for(size_t k=mid;k<i;++k) {
if(c==s[k]) {
mid=++k;
break;
}
}
if(flag) {
if(cur.count(c)==0) {
cur.insert(c);
++len;
}
else flag=false;
}
else {
int t=i-mid+1;
if(len<t) {
beg=mid;
len=t;
flag=true;
cur.clear();
for(size_t k=mid;k<=i;++k) cur.insert(s[k]);
}
}
}
return s.substr(beg,len).length();
}
};class Solution {
public:
int lengthOfLongestSubstring(string s) {
size_t beg=0,len=0,mid=0;
for (size_t i=0,j=s.size();i<j;++i){
char c=s[i];
bool flag =true;
for(size_t k=mid;k<i;++k){
if(c==s[k]){
mid=++k;
flag=false;
break;
}
}
if(flag)
if(beg==mid)
++len;
else{
size_t t=i-mid+1;
if(len<t){
beg=mid;
len=t;
}
}
}
}
return len;
}
};