题目介绍

题目来自于力扣（LeetCode）剑指 Offer 48. 最长不含重复字符的子字符串，与3. 无重复字符的最长子串属于同一题。
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是子串 的长度，”pwke” 是一个子序列，不是子串。子串是连续的；子序列不连续
提示：s.length <= 40000

问题的识别和思考

求一个不包含重复字符的子字符串在一个字符串的最长长度，如果使用暴力枚举的话，必定问题的规模非常大。所以尝试使用动态规划去解决这个问题。

DP数组的定义

首先要定义一下DP数组，按照习惯，这种DP数组的定义可以是：
字符串s[0~j]上不包含重复字符的子字符串的最长长度为dp[i]
先不管正确不正确，先尝试一下。

状态转移公式的确定

拿出一个比较正常的示例，先来手动写一下这种题目
image.png
如果给一个dp数组需要我们自己填，我们应该如何填写这个数组。
刚开始两个
image.png
p和w，两个很明显不一样，dp数组一个为1，一个为2。
s[2]这里出现了和之前一样重复的w
这个时候应该怎么处理，按照DP数组的定义：字符串s[0~j]上不包含重复字符的子字符串的最长长度为dp[i]。由于s[2]的出现，“pww“现在被破坏为一个包含重复字符的子字符串了，故dp[2] = 1。接下去继续一直更新到最后一个w出现为止，dp数组完善如下：
image.png
到了最后一个w之前，此时已经是第三次出现w了，这次的w的加入，可以看出：在w出现之前，这个字符串s的最长长度为3，最长不重复字符的子字符串为”wke“
image.png
w在加入之后，不包含重复字符的子字符串的最长长度并没有任何变化，依然是3，所以按照正常的想法，这里的dp[5]为3。
image.png
这里的dp数组虽然完善出来了，但是具体在遇到重复字符的时候，应该如何思考。也就是其状态转换是如何选择的，这是需要关注的点。

这道题目比较难以想到的就是如下几个方面

  1. 当重复字符距离上一个重复字符很近的时候，对前面构成的无重复子字符串的破坏性极其大，比如本样例当中的pww，其中第二个w直接造成前面的字符串变成了有重复字符串，dp[2]处重新回到1
  2. 当重复字符距离上一个重复很远的时候，对前面构成的无重复子字符串的破坏性较小。比如本样例当中的pwwkew，其中第三个w并没有对前面构成的最长无重复子串wke构成威胁，因为从第三个w到第二个w之间的距离是3，而wke的长度也为3。w的加入，使得新的一个无重复子串产生——ekw（同样长度也为3），wke的长度可以从dp[j-1]处获取到这个值。


再举个例子：
image.png
关注第二个k处的2是怎么来的，因为第二个k出现在第一个k的两个单位之后。第二个k的加入，导致其和前面的子串构成的不重复子字符串从wke直接变成了ek，如果在加上s[3]处的k变成kek的话，就会出现重复子字符串，所以新的不重复子字符串，也就从wke变成了ek，这里的e变成了新的不重复子字符串的第一个元素，其实这里的3，在逻辑上已经变成了1。_

所以从第二个k开始，dp[5]又再次变成了2，这个值是根据上一个k到本次的k之间的距离决定的。
所以，状态转移公式就基本确定了。
[DP、单串]最长不含重复字符的子字符串 - 图7

其他问题的思考

在这道题目里面，根据上一个相同元素到本次的元素的距离，不需要使用双重for循环去遍历求得，这里使用一个HashMap去记住“字符-上一次出现的下标”的映射即可，并且在每一次循环当中都要更新。
关于问题的BaseCase
当只有一个字符的时候，长度返回的是1，所以可以把dp[0]设置为1，并且将s[0]先放在map里面。

代码实现

  2. public int lengthOfLongestSubstring(String s) {
  3.         int len = s.length();
  4.         if (len==0){
  5.             return 0;
  6.         }
  7.         int[] dp = new int[len];
  8.         Map<Character, Integer> map = new HashMap<>();
  9.         Arrays.fill(dp,1);
  10.         map.put(s.charAt(0),0);
  11.         for (int i = 1; i < len; i++) {
  12.             if (!map.containsKey(s.charAt(i))){
  13.                 dp[i] = dp[i-1]+1;
  14.             }else{
  15.                 int lastIndex = map.get(s.charAt(i));
  16.                 int dist = i-lastIndex;
  17.                 dp[i] = dist>dp[i-1]?dp[i-1]+1 :dist;
  18.             }
  19.             map.put(s.charAt(i),i);
  20.         }
  21.         return Arrays.stream(dp).max().getAsInt();
  22.     }

代码其实还有优化的地方，比如空间复杂度可以降低到O(1)，因为只需要上一次d[j-1]的状态的读取，所以完全可以把本次的dp[i]值存放起来，放在一个变量prev当中，供下次的dp[i+1]使用。

代码的表现虽然不是很好，时间复杂度略高，但是思路很重要。

  • 看清楚是子字符串还是子序列。
  • 在分析状态转换的时候，一定要仔细审查，反复确认是否符合dp数组的定义
  • 针对“重复”出现的字符串，要特别小心有几种可能的转换。