题解 | #最长不含重复字符的子字符串#

题目的主要信息：

• 从一个字符串中找一个最长的一段不含重复字符的子串，求长度
• 子串必须是字符串中连续的部分

举一反三：

学习完本题的思路你可以解决如下题目：

JZ46. 把数字翻译成字符串

JZ59. 滑动窗口的最大值

方法一：滑动窗口+哈希表（推荐使用）

知识点1：滑动窗口

滑动窗口是指在数组、字符串、链表等线性结构上的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。我们在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。

知识点2：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

既然要找一段连续子串的内不重复的长度，我们可以使用滑动窗口，保证窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复字符，说明新加入的元素与之前的重复了，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的。

而保证窗口内的元素不重复，我们可以使用根据key值快速访问的哈希表，key值为窗口内的元素，value为其出现次数，只要新加入窗口的元素出现次数不为1，就是重复。

while(mp.get(s.charAt(right)) > 1) 
    //窗口左移，同时减去该数字的出现次数
    mp.put(s.charAt(left), mp.get(s.charAt(left++)) - 1);  

具体做法:

• step 1：构建一个哈希表，用于统计字符元素出现的次数。
• step 2：窗口左右界都从字符串首部开始，每次窗口优先右移右界，并统计进入窗口的元素的出现频率。
• step 3：一旦右界元素出现频率大于1，就需要右移左界直到窗口内不再重复，将左边的元素移除窗口的时候同时需要将它在哈希表中的频率减1，保证哈希表中的频率都是窗口内的频率。
• step 4：每轮循环，维护窗口长度最大值。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int lengthOfLongestSubstring (String s) {
        //哈希表记录窗口内非重复的字符
        HashMap<Character, Integer> mp = new HashMap<>(); 
        int res = 0;
        //设置窗口左右边界
        for(int left = 0, right = 0; right < s.length(); right++){ 
            //窗口右移进入哈希表统计出现次数
            if(mp.containsKey(s.charAt(right)))
                mp.put(s.charAt(right), mp.get(s.charAt(right)) + 1); 
            else
                mp.put(s.charAt(right), 1);
            //出现次数大于1，则窗口内有重复
            while(mp.get(s.charAt(right)) > 1) 
                //窗口左移，同时减去该字符的出现次数
                mp.put(s.charAt(left), mp.get(s.charAt(left++)) - 1); 
            //维护子串长度最大值
            res = Math.max(res, right - left + 1); 
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //哈希表记录窗口内非重复的字符
        unordered_map<char, int> mp; 
        int res = 0;
        //设置窗口左右边界
        for(int left = 0, right = 0; right < s.length(); right++){ 
            //窗口右移进入哈希表统计出现次数
            mp[s[right]]++; 
            //出现次数大于1，则窗口内有重复
            while(mp[s[right]] > 1) 
                //窗口左移，同时减去该字符的出现次数
                mp[s[left++]]--; 
            //维护子串长度最大值
            res = max(res, right - left + 1); 
        }
        return res;
    }
};

Python实现代码：

class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        #哈希表记录窗口内非重复的字符
        mp = dict()
        res = 0
        #设置窗口左右边界
        left = 0
        right = 0
        while(right < len(s)):
            #窗口右移进入哈希表统计出现次数
            if s[right] in mp:
                mp[s[right]] += 1
            else:
                mp[s[right]] = 1
            #出现次数大于1，则窗口内有重复
            while mp[s[right]] > 1:
                #窗口左移，同时减去该字符的出现次数
                mp[s[left]] -= 1
                left += 1
            #维护子串长度最大值
            res = max(res, right - left + 1)
            right += 1
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串的长度，外循环窗口右界从字符串首右移到数组尾，内循环窗口左界同样如此，因此复杂度为$O(n+n)=O(n)O(n+n)=O(n)$
• 空间复杂度：$O(n)O(n)$，最坏情况下整个字符串都是不重复的，哈希表长度就为字符串长度$nn$

方法二：动态规划+哈希表（扩展思路）

知识点：

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

如果对于某个前面的子串，如果我们新加入一个字符，与前面的都不重复，那么最长无重复子串肯定就是在前面的基础上加1，如果与前面重复了，那就是当前位置减去它重复之前字符出现的位置的长度。因此我们使用动态规划递推。

具体做法：

• step 1：$dp[i]dp[i]$表示以下标i结尾的字符串最长不含重复子串的长度，用哈希表记录是否重复出现字符，并记录其位置。
• step 2：遍历字符串，哈希表中没有出现过的就不是重复，因此考虑$dp[i]=dp[i-1]+1dp[i]\; =\; dp[i\; -\; 1]\; +\; 1$，即在前一个字符的基础上加上它。
• step 3：哈希表中出现过的，这是重复的字符，考虑$i-mp[s[i-1]]i\; -\; mp[s[i\; -\; 1]]$，但是为了防止中间出现其他重复的字符，还是应该考虑它的前一个字符的基础，因此实际转移方程为$dp[i]=min(dp[i-1]+1,i-mp[s[i-1]])dp[i]\; =\; min(dp[i\; -\; 1]\; +\; 1,\; i\; -\; mp[s[i\; -\; 1]])$。
• step 4：遍历过程中遇到的字符都要加入哈希表，同时维护最大的长度。

Java实现代码：

import java.util.*;
public class Solution {
    public int lengthOfLongestSubstring (String s) {
        //哈希表记录窗口内非重复的字符及其下标
        HashMap<Character, Integer> mp = new HashMap<>(); 
        int res = 0;
        //dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        int[] dp = new int[s.length() + 1];
        for(int i = 1; i <= s.length(); i++){
            dp[i] = 1;
            //哈希表中没有，说明不重复
            if(!mp.containsKey(s.charAt(i - 1)))
                //前一个加1
                dp[i] = dp[i - 1] + 1;
            //遇到重复字符
            else
                dp[i] = Math.min(dp[i - 1] + 1, i - mp.get(s.charAt(i - 1)));
            //加入哈希表
            mp.put(s.charAt(i - 1), i);
            //维护最大值
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //哈希表记录窗口内非重复的字符及其下标
        unordered_map<char, int> mp; 
        int res = 0;
        //dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        vector<int> dp = vector<int>(s.length() + 1, 0);
        for(int i = 1; i <= s.length(); i++){
            dp[i] = 1;
            //哈希表中没有，说明不重复
            if(mp.find(s[i - 1]) == mp.end())
                //前一个加1
                dp[i] = dp[i - 1] + 1;
            //遇到重复字符
            else
                dp[i] = min(dp[i - 1] + 1, i - mp[s[i - 1]]);
            //加入哈希表
            mp[s[i - 1]] = i;
            //维护最大值
            res = max(res, dp[i]);
        }
        return res;
    }
};

Python实现代码：

class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        #哈希表记录窗口内非重复的字符及其下标
        mp = dict()
        res = 0
        #dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        dp = [0 for i in range(len(s) + 1)]
        for i in range(1, len(s) + 1):
            dp[i] = 1
            #哈希表中没有，说明不重复
            if s[i - 1] not in mp:
                #前一个加1
                dp[i] = dp[i - 1] + 1
            #遇到重复字符
            else:
                dp[i] = min(dp[i - 1] + 1, i - mp[s[i - 1]])
            #加入哈希表
            mp[s[i - 1]] = i
            #维护最大值
            res = max(res, dp[i])
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，遍历一次字符串
• 空间复杂度：$O(n)O(n)$，辅助数组dp的大小为字符串长度，哈希表的最大空间为字符串长度