题目描述

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

示例

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

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

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

解题想法

这道题想通了发现也是一道比较常规的动态规划题，但是开始时没有考虑好的细节确实是折磨了我一阵。以及没有想到用哈希表处理属实比较蠢。

动态规划

1、状态的定义，本题依旧需要一个一维的动态规划数组，dp[i]则表示以第i个字符为结尾的子字符串可以得到的最长的含不重复字符的子字符串长度。

2、状态转移方程，首先我们需要固定右边界i，也就是遍历时的索引，设与s[i]相同且距离最近的字符为s[pos]（pos初始化为-1。此时不重复字符子串长度应该是i - pos，但是题目所求为最长，因此根据动态规划的思想就有以下的情况

（a）、当$pos<0$时，说明在s[i]的左侧没有与s[i]相同的字符，那么dp[i] = dp[i - 1] + 1（即最长长度等于遍历到前一字符的长度 + 1）

（b）、当$dp[i - 1]<i - pos$时，说明重复的字符应该在当前最长非重复字符子串的区间外，即在这个子串的左边，此时dp[i] = dp[i - 1] + 1，也就是之前的子串再加上当前的字符。

（c）、当$dp[i - 1]>=i-pos$​时，说明此时重复的字符应该在当前最长的非重复字符子串的区间内，因此dp[i] = i - pos，也就是在之前的子串中截取出非重复的部分。

3、需要一个哈希表用来记录曾经出现过的字符的相对应的索引，每当遍历到一个重复字符时，便要将哈希表中的相应表项更新为当前的索引。

由以上的分析可以看出，dp[i]只由dp[i - 1]决定，所以可以省略动态规划的数组，采用一个变量进行迭代即可，并求取此变量在这个过程中的最大值。

双指针法（滑动窗口）

由于滑动窗口的代码写得比较少，当看到题解有滑动窗口时，便又学习了一下。

首先要初始化left = -1以及right = 0两个指针，利用right指针进行遍历，并根据是否有重复的字符，以及是否为最长的子字符串来更改left指针的位置。这种做法依旧需要一个哈希表来存储字符对应的索引。这样就会有以下两种情况。

（a）、当right指针对应的字符在哈希表中不存在时，可以直接增加right指针的值，且子字符串长度为right - left

（b）、若right指针对应的字符在哈希表中存在，那么需要将left更改为当前的left指针与哈希表中对应索引的最大值（这里很重要，如果没有取两者之间的最大值那么虽然可以避免在左右两个端点处重复，但可能会导致在字符串内存在重复字符）。

在每次更新最长字符串的值之前都要更新哈希表中的相应表项。

代码

/*动态规划*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.size()) return 0;
        if (s.size() == 1) return 1;  // 优先判断两种特殊情况
        int res = 1, len = s.size();
        unordered_map<char, int> um;  // 用于存储字符的索引位置
        int temp = 0;  // temp用来存储上一次的dp值
        for (int i = 0; i < len; ++i) {
            int pos;  // 用来获取是否有当前字符的索引
            if (um.count(s[i])) pos = um[s[i]];
            else pos = -1;
            um[s[i]] = i;  // 更新哈希表的索引
            temp = (i - pos) > temp ? temp + 1 : (i - pos);
            res = max(res, temp);
        }
        return res;
    }
};

/*滑动窗口*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.size()) return 0;
        if (s.size() == 1) return 1;  // 优先判断两种特殊情况
        unordered_map<char, int> um;
        int left = -1, len = s.size();
        int res = 1;
        for (int right = 0; right < len; ++right) {
            if (um.count(s[right])) {  // 表明这时候已经出现的重复的字符
                // 这时候需要移动左指针
                left = max(left, um[s[right]]);  // 如果不取两者最大，那么会可能会导致字符串内重复
            }
            um[s[right]] = right;  // 更新索引
            res = max(res, right - left);
        }
        return res;
    }
};