题目链接

LeetCode

题目描述

输入一个字符串（只包含 a~z 的字符），求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4。

解题思路

动态规划

动态规划解析：
  • 状态定义： 设动态规划列表 dp ，dp[j] 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度。
  • 转移方程： 固定右边界 j ，设字符 s[j] 左边距离最近的相同字符为 s[i] ，即 s[i] = s[j] 。
    1. 当 i < 0 ，即 s[j] 左边无相同字符，则 dp[j] = dp[j-1] + 1 ；
    2. 当 dp[j - 1] < j - i，说明字符 s[i] 在子字符串 dp[j-1] 区间之外，则 dp[j] = dp[j - 1] + 1 ；
    3. 当 dp[j−1]≥j−i,说明字符 s[i] 在子字符串 dp[j-1] 区间之中,则 dp[j] 的左边界由 s[i] 决定,即 dp[j] = j - i ；
  • 返回值： max(dp) ，即全局的 “最长不重复子字符串” 的长度。

当 i < 0 时，由于 dp[j−1]≤j 恒成立，因而 dp[j−1]48. 最长不含重复字符的子字符串 - 图1

方法一：动态规划 + 哈希表

  • 哈希表统计： 遍历字符串 s 时，使用哈希表（记为 dic ）统计 各字符最后一次出现的索引位置 。
  • 左边界 i 获取方式： 遍历到 s[j] 时，可通过访问哈希表 dic[s[j]] 获取最近的相同字符的索引 i 。
  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         int len = s.length(),ret=0,tmp=0;
  5.         unordered_map<char,int> mp;
  6.         for(int j=0;j<len;j++){
  7.             auto it = mp.find(s.at(j));
  8.             int i=-1;
  9.             if(it!=mp.end()){ // 获取索引 i
  10.                 i = it->second;
  11.             }else{
  12.                 i=-1;
  13.             }
  14.             mp[s.at(j)]=j;    // 更新哈希表
  15.             if(tmp<j-i){    // dp[j - 1] -> dp[j]
  16.                 tmp = tmp+1;
  17.             }else{
  18.                 tmp = j-i;
  19.             }
  20.             ret = max(ret,tmp);// max(dp[j - 1], dp[j])
  21.         }
  22.         return ret;
  23.     }
  24. };
  • 时间复杂度 O(N) ： 其中 N 为字符串长度，动态规划需遍历计算 dp 列表。
  • 空间复杂度 O(1) ： 字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间。

方法二：双指针 + 哈希表

  • 哈希表 dic 统计： 指针 j 遍历字符 s ，哈希表统计字符 s[j] 最后一次出现的索引 。
  • 更新左指针 i ： 根据上轮左指针 i 和 dic[s[j]] ，每轮更新左边界 i ，保证区间 [i + 1, j] 内无重复字符且最大。

i=max(dic[s[j]],i)

  • 更新结果 res ： 取上轮 res 和本轮双指针区间 [i + 1,j] 的宽度（即 j - i ）中的最大值。

res=max(res,j−i)

  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         int len = s.length();
  5.         if(len<2)
  6.             return len;
  8.         unordered_map<char,int> mp;
  9.         int res=0,i=-1;
  10.         for(int j=0;j<len;j++){
  11.             auto it = mp.find(s[j]);
  12.             if(it!=mp.end())
  13.                 i = max(i,it->second);// 更新左指针 i
  14.             mp[s[j]] = j;// 哈希表记录
  15.             res = max(res,j-i);// 更新结果
  16.         }
  17.         return res;
  18.     }
  19. };
  21. class Solution {
  22. public:
  23.     int lengthOfLongestSubstring(string s) {
  24.         int len = s.length();
  25.         if(len<2)
  26.             return len;
  27.         int left = 0,right = 1;
  28.         int ans = 1;
  29.         while(right<len){
  30.             for(int i=left;i<right;i++){
  31.                 if(s[i]==s[right]){
  32.                     left = i+1;
  33.                     break;
  34.                 }
  35.             }
  36.             right++;
  37.             ans = max(ans,right-left);
  38.         }
  39.         return ans;
  40.     }
  41. };
  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int res = 0;
  4.         int right = 0;
  5.         Set<Character> set = new HashSet<>();
  6.         for(int i = 0; i < s.length(); ++i){
  7.             if(i != 0){
  8.                 set.remove(s.charAt(i-1));
  9.             }
  10.             while(right < s.length() && !set.contains(s.charAt(right))){
  11.                 set.add(s.charAt(right));
  12.                 ++right;
  13.             }
  14.             res = Math.max(res, right - i);
  15.         }
  16.         return res;
  17.     }
  18. }
  • 时间复杂度 O(N) ： 其中 N 为字符串长度，动态规划需遍历计算 dp 列表。
  • 空间复杂度 O(1) ： 字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128)=O(1) 大小的额外空间。