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

今天处理一道算法题目，《剑指Offer》第48题，力扣中等题。

这道题也是面试的高频题！

题目描述

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

示例1：

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

示例 2:

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

示例 3:

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

解题思路

方法1：动态规划

用f(i)表示以第i个字符为结尾的不含重复字符的最长长度，推断出三种情况：

1. 如果当前字符在之前都没出现过，那么f(i) = f(i-1) + 1;

2. 如果当前字符在之前出现过，并且两者的距离差d<=f(i-1)，那么当前的最长长度即为d；

3. 如果当前字符在之前出现过，并且两者的距离差d>f(i-1)，那么说明之前的这个元素已经在滑动窗口之外，我们仍然可以用f(i) = f(i-1)+1;

/*** 动态规划*设f(i)表示以第i个字符为结尾的不含重复字符的最长长度，可以得到状态转换方程：f(i)={f(i-1)+1; 第i个字符之前没出现过d; 之前出现过，但和之前出现的字符距离差d小于等于f(i-1)，即d<f(i-1)f(i-1)+1; 之前出现过，且d>f(i-1)}// 以arabcacfr为例，在计算最后一个r，即f(8)的时候，出现d>f(7)的情况，可以把r追加到f(7)的后面这个思路是最通俗易懂的，但代码和时间上不是最优的* @param s* @return*/public int lengthOfLongestSubstring(String s) {if(s == null || s.length() == 0)return 0;int n = s.length();if(n == 1)return 1;int[] mem = new int[n];Map<Character, Integer> map = new HashMap<>();//初始化mem[0] = 1;map.put(s.charAt(0), 0);for(int i = 1; i < n; ++i) {char c = s.charAt(i);//之前没有出现过，则f(i) = f(i-1)+1if(!map.containsKey(c)) {map.put(c, i);mem[i] = mem[i-1] + 1;}else{//之前出现过，记录差值d，并比较差值和f(i-1)的大小int before = map.get(c);int d = i - before;if(d <= mem[i-1]) {mem[i] = d;}else {mem[i] = mem[i-1]+1;}//最后记得更新这个值map.put(c, i);}}int maxLen = 0;for(int i = 0; i < n; ++i) {maxLen = Math.max(maxLen, mem[i]);}return maxLen;}

总体来说，这种方法时间不是最优，但思路很清晰。

方法2：滑动窗口

用i,j两个指针来控制窗口的左右边界，然后用i每次递增一隔，计算以i为起点的最长无重复子串，只是这里的j不用从i的位置开始，这种做法也是力扣官方的做法，个人觉得不太好，时间复杂度不高。

/*** 滑动窗口（或者就左右指针）* @param s* @return*/public int lengthOfLongestSubstring2(String s) {//abcabcbbif(s == null || s.length() == 0)return 0;int n = s.length();if(n == 1)return 1;Set<Character> set = new HashSet<>();int i = 0;set.add(s.charAt(0));int j = 1;int maxLen = 0;while(i < n) {while(j < n) {char c = s.charAt(j);if(set.contains(c)){break;}set.add(c);j++;}maxLen = Math.max(maxLen, j-i);set.remove(s.charAt(i));i++;}return maxLen;}

方法3：左右指针

该方法是极力推荐的做法：用j遍历字符串，每次判断以j为结尾的最长无重复字符的子串长度，如果出现了重复字符，则更新左边界。只是这里，需要额外注意，更新左边界的时候，需要取上一个左边界和当前元素对应的之前值的最大值。

/*** 左右指针，j表示以第j个字符为结尾的不含重复字符的最长子串* 这里必须要注意一种情况，就是左边界需要取原左边界和当前元素在map中保存的值的最大值* 防止类似于abba这种字符串* @param s* @return*/public int lengthOfLongestSubstring3(String s) {if (s == null || s.length() == 0)return 0;int n = s.length();int i = -1;int maxLen = 0;Map<Character, Integer> map = new HashMap<>();for (int j = 0; j < n; ++j) {if (map.containsKey(s.charAt(j))) {i = Math.max(i, map.get(s.charAt(j)));}map.put(s.charAt(j), j);maxLen = Math.max(maxLen, j - i);}return maxLen;}