LeetCode 3:无重复字符的最长子串 思考分析

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:

输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:

输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

动态规划解

dp[i]：到以第i个字符结尾的不包含重复字符的最大长度 对于第i个字符： 1、第i个字符从未出现过，dp[i]=dp[i-1]+1 2、第i个字符出现过：找到第i个字符最近一次出现的位置index(从第i个往前找),记两个距离为d=i-index 【a】、d<= dp[i-1],即这个字符出现在以第i-1个字符结尾的不含重复字符的字符串中,则dp[i]=d,表示从第最近一次出现后重新计算长度： 例如： i: 0 1 2 3 4 5 s: 1 2 3 4 5 4 dp: 1 2 3 4 5 2 最后的这个2 = 5 - 3（最近一次出现的i）； 【b】、d>dp[i-1],即这个字符没有出现在以第i-1字符结尾的不含重复的最大长度字符串中。 dp[i] = dp[i-1] +1; 例如： i: 0 1 2 3 4 5 6 s: 1 2 3 4 5 4 1 dp: 1 2 3 4 5 2 3 s最后的这个1虽然在i=0的位置出现过，但是由于d=6-0=6>dp[5],所以dp[6]=dp[5]+1,也就是说我们的子串已经重新更新了。

class Solution { public: int lengthOfLongestSubstring(string s) { unordered_set<char> myset; int sz = s.size(); int ans = 1; if (sz == 0) return 0; vector<int> dp(sz, 0); dp[0] = 1; for (int i = 0;i < sz;i++) //起点 { //如果第i个字符出现过 if (myset.find(s[i]) != myset.end()) { if (i >= 1) { int index = get_index(s, s[i],i); if (index == -1) index = 0; int d = i - index; if (d <= dp[i - 1]) dp[i] = d; else dp[i] = dp[i - 1] + 1; } } //如果没有出现过，记录下来 else { myset.insert(s[i]); if (i >= 1) { dp[i] = dp[i - 1] + 1; } } ans = max(ans, dp[i]); } return ans; } int get_index(string s, char x,int start) { int sz = s.size(); if (sz == 0) return -1; for (int i = start-1;i >=0 ;i--) { if (s[i] == x) return i; } return -1; //没有找到 } };

参考https://zhuanlan.zhihu.com/p/112545613进行优化;

f[i]：以原字符串s中，以位置i的字符s[i]为右边界时的最优左边界 例如样例 a b c a b c b b 对应的f数组为： f[0] = 0，左边界为第一个a，对应子串为a f[1] = 0，左边界为第一个a，对应子串为ab f[2] = 0，左边界为第一个a，对应子串为abc f[3] = 1，左边界为第一个b，对应子串为bca f[4] = 2，左边界为第一个c，对应子串为cab f[5] = 3，左边界为第二个a，对应子串为abc f[6] = 5，左边界为第二个c，对应子串为cb f[7] = 7，左边界为最后一个b，对应子串为b f[0] = 0; 对于f[i],只需要考察f[i-1]到i-1这个区间中是否出现过s[i] 如果没有出现过，则f[i]=f[i-1] 如果出现过，那么必然只出现了一次，因为f[i-1]到i-1这个区间中必然不存在重复字符，于是设s[i]出现的位置为pos，则f[i]=pos+1;在重复的字符后面的一个字符作为新的起始点。 可以发现，左边界的更新是单调递增的，因此s中每个字符最多也只会遍历一遍，时间复杂度为O(n)。 由于f[i]的更新只与f[i-1]有关，因此不需要维护整个数组。

class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ left = 0 res = 0 for right,char in enumerate(s): pos = s.find(char,left,right) if pos >=0: left = pos+1 else: left = left res = max(res,right-left+1) return res

滑动窗口解

其实和dp第一种方法类似： 滑动窗口的核心思路如下： 比如输入字符串为：abcdecfg，字串 abcde 满足题目要求，当新加入 c 时，字串变成了 abcde c，字符 c 重复了，不满足要求。这时候，只需要将第一个重复的字符 c 连同之前的字符丢掉，变成 de c，就又能满足要求了。每新加一个字符，都更新最长字串的长度，遍历完一遍之后，即可得到答案。 问题在于如何丢掉第一个重复字符连同之前的字符，其实我们不用真的丢掉，而是可以维护一个左边界值 left ，有重复字符的话，就把 left 更新为重复字符的下一个位置，假装丢掉了它和之前的字符。 参考链接:https://blog.csdn.net/m0_37433111/article/details/108743399

class Solution { public: int lengthOfLongestSubstring(string s) { int sz = s.size(); if (sz == 0) return 0; int left=0; int maxlen=1; // val存放字符在原字符串的索引 unordered_map<char,int> u_map; for (int i = 0;i < sz;i++) //起点 { //如果有重复的字符，左边界更新到重复的字符后面一个 if(u_map.find(s[i])!=u_map.end()) left = max(left,u_map[s[i]]+1); //如果没有重复的字符，左边界保持不变也就是left=left,可以省略不写 //将s[i]插入、 u_map[s[i]] = i; //如果有重复的，则将坐标更新为靠后的坐标 // 更新最长子串的长度 maxlen = max(maxlen,i-left+1); } return maxlen; } };