最长不含重复字符的子字符串

问题描述

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

示例 1:

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

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

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

分析

此题是一个动态规划问题，假设s表示问题中的字符串，dp[i]表示以第i个字符结尾的最长不含重复字符的子字符串长度。我们从前往后依次扫描字符串，每扫描一个字符(s[i])，都将它与以它前一个字符结尾(s[i-1])的最长不重复子串作对比。 如果s[i]不在这个子串中，那么可以将它加入该子串，子串长度加一。 如果s[i]在这个子串中，那么从s[i]这个字符上次出现的位置(假设下标为j)的下一位到i的距离为子串的长度。 所以可以得到状态转移方程： 如果s[i]不在这个子串中 ： dp(i) = dp(i-1)+1 如果s[i]在这个子串中：dp(i) = i - j 注意：新状态只与上一状态有关，所以只需要一个临时变量记录当前子串长度即可。 因为我们动态规划的已经包含了当前子串的长度，所以只需要找到s[i]这个字符上次出现的位置到i的距离，再与子串长度作对比。

代码

下面给出两种方法

方法一：哈希表

class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> dic = new HashMap<>(); int res = 0, temp = 0; for(int i = 0; i < s.length(); i++){ int pre_index = dic.getOrDefault(s.charAt(i), -1); dic.put(s.charAt(i), i); if(temp < i - pre_index) temp++; else temp = i - pre_index; res = Math.max(temp,res); } return res; } }

方法二：线性查找

class Solution { public int lengthOfLongestSubstring(String s) { int res = 0, temp = 0; for(int i = 0; i < s.length(); i++){ int pre_index = i - 1; while(pre_index >= 0 && s.charAt(pre_index) != s.charAt(i)) pre_index--; if(temp < i - pre_index) temp++; else temp = i - pre_index; res = Math.max(temp,res); } return res; } }

复杂度分析

使用哈希表的时间复杂度为O(N), 空间复杂度为O(1) 线性查找的时间复杂度为O(N^2),空间复杂度为O(1)