dp表当前为结尾的最长结果
讨论两种情况:
1,之前不存在,就拼接在后面
2,之前存在,再分两种讨论
a 出现过的字符在最长结果里
b 出现过的字符不在最长结果里
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
int lengthOfLongestSubstring(string s) {
// write code here
int dp[50000];
map<char,int> mp;
dp[0]=1;
mp[s[0]]=0;
int ans=1;
for(int i=1;i<s.size();i++){
if(mp.count(s[i])){
dp[i]=min(dp[i-1]+1,i-mp[s[i]]);
mp[s[i]]=i;
}else{
mp[s[i]]=i;
dp[i]=dp[i-1]+1;
}
// cout<<i<<" :"<<dp[i]<<endl;
ans=max(ans,dp[i]);
}
return ans;
}
};