剑指offer(C++)-JZ48：最长不含重复字符的子字符串(算法-动态规划)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

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

数据范围:

 s.length≤40000 s.length≤40000

示例：

输入：

"abcabcbb"

返回值：

3

说明：

因为无重复字符的最长子串是"abc"，所以其长度为 3。 

解题思路：

本题是动态规划的经典题目。有两个解题思路。

思路一：滑动窗口

1. 设计一个滑动窗口，窗口的右边界先行，用哈希表统计字符出现次数。
2. 当出现重复字符时，左边界出发缩小窗口直到重复字符消失。
3. 持续刷新最值就可以了。

思路二：动态规划

1. 用哈希表存放字符上次出现的位置下标；用长度比字符串大1的vector，存放截止到第i个字符时，能继续维持的子串长度，比如v[0]=0，v[1]=1，v[2]可能为1可能为2。
2. 执行遍历。用哈希表判断当前字符是否为重复字符，如果不是重复字符，那就在前面子串长度基础上加1；若出现了重复字符，则该字符与其重复字符的距离为i-m[s[i]]，但如果两者之间有别的重复字符，则需要考虑此类情况，可以认为在其重复字符之后的子串中，该字符未出现过，则有v[i]+1；所以，比较v[i]+1和i-m[s[i]]谁小取谁，因为小的子串没断开，后续可以继续连接，而断开的子串虽然长度大，但不可以继续增加了。
3. 持续更新字符最新下标以及子串长度最大值。

测试代码：

思路一：滑动窗口

class Solution {
public:
    // 最长子串
    int lengthOfLongestSubstring(string s) {
        // 定义哈希表
        unordered_map<char, int> m;
        // 滑动窗口遍历
        int result = 0;
        for(int left = 0, right = 0; right < s.length(); ++right){
            // 窗口右边界先行，统计字符出现次数
            m[s[right]]++;
            // 当出现重复字符，窗口左边界右移缩小窗口直到重复字符消失
            while(m[s[right]] > 1){
                m[s[left]]--;
                left++;
            }
            // 持续刷新子串最大长度
            result = max(result, right - left + 1);
        }
        return result;
    }
};

思路二：动态规划

class Solution {
public:
    // 最长子串
    int lengthOfLongestSubstring(string s) {
        // 定义哈希表，存放的是字符出现的位置下标
        unordered_map<char, int> m;
        int result = 0;
        // v[i]表示截止到i个字符时，能继续维持的子串长度
        // 所以v[0]=0,v[1]=1
        vector<int> v = vector<int>(s.length() + 1, 0);
        // i是字符串中字符下标
        for(int i = 0; i < s.length(); ++i){
            // 当哈希表中没发现重复字符，那就在前面最长子串长度基础上+1
            if(m.find(s[i]) == m.end())
                v[i + 1] = v[i] + 1;
            // 若出现了重复字符，该字符与其重复字符的距离为i-m[s[i]]
            // 但如果两者之间有别的重复字符，那要考虑这类情况
            // 可以认为在其重复字符之后的子串中，该字符未出现过，则有v[i]+1
            // 所以v[i]+1和i-m[s[i]]谁小，取谁，因为小的这个子串没断开
            else
                v[i + 1] = min(v[i] + 1, i - m[s[i]]);
            // 刷新该字符最新下标
            m[s[i]] = i;
            // 刷新最值
            result = max(result, v[i + 1]);
        }
        return result;
    }
};