剑指offer面试题48最长不含重复字符的子字符串

问题&＃xff1a;请从字符串中找出一个最长的不包含重复字符的子字符串&＃xff0c;计算该最长子字符串的长度。

输入&＃xff1a;字符串

输出&＃xff1a;最长子字符串的长度

思路&＃xff1a;动态规划

定义f(i)表示以第i个字符为结尾的不包含重复字符的子字符串的最长长度。

如果第i个字符之前没有出现过&＃xff0c;那么f(i)&＃61;f(i-1)&＃43;1&＃xff0c;

如果第i个字符之前出现过&＃xff0c;先计算与它上次出现位置的距离&＃xff0c;如果d小于等于f(i-1)&＃xff0c;则f(i)&＃61;d&＃xff0c;如果d大于f(i-1)&＃xff0c;则f(i)&＃61;f(i-1)&＃43;1&＃xff0c;

代码&＃xff1a;

class Solution {
public:int lengthOfLongestSubstring(string s) {vector index(256,-1);int len&＃61;s.size();if(len&＃61;&＃61;0)return 0;vector dp(len);dp[0]&＃61;1;index[s[0]-&＃39; &＃39;]&＃61;0;for(int i&＃61;1;idp[i-1])dp[i]&＃61;dp[i-1]&＃43;1;elsedp[i]&＃61;i-prevIndex;index[s[i]-&＃39; &＃39;]&＃61;i;}return *max_element(dp.begin(),dp.end());}
};

复杂度分析&＃xff1a;时间复杂度为O(n)&＃xff0c;空间复杂度为O(n).