剑指 Offer 48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

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

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

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

• s.length <= 40000

解题思路：

​ 这题可以用动态规划来分析：

• 状态定义： 设动态规划列表dp，dp[j] 代表以字符s[j] 为结尾的 “最长不重复子字符串”的长度

• 转移方程： 固定右边界j，设字符串s[j] 左边距离最近的相同的字符串为s[i] ，s[i] = s[j]

  • 当i < 0,说明s[j]左边没有相同字符，dp[j] = dp[j-1] + 1
  • 当dp[j-1] < j - i ,说明s[i] 在子字符串dp[j-1]区间之外，那么dp[j] = dp[j-1] + 1
  • 当dp[j-1]>j - i,说明s[i] 在子字符串dp[j-1]区间之中，那么dp[j] = j - i；

• 那么得出状态转移方程

  dp[j] = dp[j-1] + 1; (dp[j-1] < j - i)

  dp[j] = j - i; (dp[j-1] >= j - i)

• 返回值返回max(dp)，利用循环赋值找最大值即可

AC代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0,tmp = 0;
        for(int j = 0;j < s.size();j++)
        {
            int i = j-1;
            while(i>=0&&s[i]!=s[j]) i--;		//线性遍历寻找s[i] == s[j]中i的下标
            tmp = tmp < j-i?tmp+1:j-i;			//状态转移方程组
            res = max(res,tmp);					//循环赋值寻找最大值
        }
        return res;								//返回dp最大值
    }
};