题目的主要信息:
  • 从一个字符串中找一个最长的一段不含重复字符的子串,求长度
  • 子串必须是字符串中连续的部分
举一反三:

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

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:每轮循环,维护窗口长度最大值。

图示:

alt

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[i1]+1dp[i] = dp[i - 1] + 1,即在前一个字符的基础上加上它。
  • step 3:哈希表中出现过的,这是重复的字符,考虑imp[s[i1]]i - mp[s[i - 1]],但是为了防止中间出现其他重复的字符,还是应该考虑它的前一个字符的基础,因此实际转移方程为dp[i]=min(dp[i1]+1,imp[s[i1]])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的大小为字符串长度,哈希表的最大空间为字符串长度