java - 不包含重复字符的最长公共(public)子串的长度

Question

给定“abcabcbb”，答案是“abc”，长度为3。

给定“bbbbb”，答案是“b”，长度为1。

给定“pwwkew”，答案是“wke”，长度为3。注意，答案必须是子字符串，“pwke”是子序列而不是子字符串。

我提出了一个可行的解决方案，但在几个测试用例中失败了。然后我找到了一个更好的解决方案，并重写了它以尝试理解它。下面的解决方案工作完美，但经过大约 2 个小时的研究，我仍然无法理解为什么这行特定的代码有效。

import java.util.*;
import java.math.*;

public class Solution {

  public int lengthOfLongestSubstring(String str) {

  if(str.length() == 0)
    return 0;

  HashMap<Character,Integer> map = new HashMap<>();
  int startingIndexOfLongestSubstring = 0;
  int max = 0;

  for(int i = 0; i < str.length(); i++){
      char currentChar = str.charAt(i); 
      if(map.containsKey(currentChar))
         startingIndexOfLongestSubstring = Math.max(startingIndexOfLongestSubstring, map.get(currentChar) + 1);

      map.put(currentChar, i);
      max = Math.max(max, i - startingIndexOfLongestSubstring + 1);

      }//End of loop

    return max;

   }
}

有问题的行是

max = Math.max(max, i - startingIndexOfLongestSubstring + 1);

我不明白为什么会这样。我们取之前最大值之间的最大值，以及当前索引与当前最长子字符串的起始索引之间的差值，然后加 1。我知道代码正在获取当前索引与当前索引之间的差值。 startingIndexOfSubstring，但我无法概念化为什么它可以给我们预期的结果；有人可以向我解释一下这个步骤，特别是为什么它有效吗？

Answer 1

我通常不擅长解释，让我通过考虑一个例子来尝试一下。

字符串是“wcabcdeghi”。

暂时忘记代码，假设我们正在尝试找出一个逻辑。

1. 我们从 w 开始，一直前进，直到到达 c -> a -> b -> c。
   我们需要在此时停止，因为“c”正在重复。所以我们需要一个映射来存储某个字符是否重复。 (在代码中: map.put(currentChar, i); )
2. 现在我们知道一个字符是否重复，我们需要知道最大值是多少。到目前为止的长度。 (在代码中-)max
3. 现在我们知道跟踪前 2 个变量 w->c 的计数是没有意义的。这是因为包括这个在内，我们已经得到了Max。值(value)。因此，从下一次迭代开始，我们只需检查 a -> b -> 的长度。
   让我们有一个变量(在代码中-)startingIndexOfLongestSubstring来跟踪这一点。 (这应该被命名为startingIndexOfNonRepetativeCharacter，但我又不擅长命名)。
4. 现在我们再次继续，但是等等，我们仍然没有最终确定如何跟踪我们当前正在解析的子字符串。 (即，从 abcd...)
   想想看，我需要的只是“a”出现的位置(即 startingIndexOfNonRepetativeCharacter )，所以要知道当前子字符串的长度，我需要做的就是(在代码中 -) i - startingIndexOfLongestSubstring + 1 (当前字符位置 - 非重复字符长度+(减法不能包含两边，所以加 1)。我们称之为 currentLength
5. 但是等等，我们要如何处理这个计数。每次我们找到一个新变量时，我们都需要检查是否是 currentLength可以打破我们的最大值。 所以(在代码中-)max = Math.max(max, i - startingIndexOfLongestSubstring + 1);
6. 现在我们已经涵盖了我们需要的大部分语句，根据我们的逻辑，每次遇到已经存在的变量时，我们需要的是 startingIndexOfLongestSubstring = map.get(currentChar) 。那么我们为什么要做 Max ？
   考虑字符串为“wcabcdewghi”的场景。当我们开始将新计数器处理为 a -> b -> c -> d -> e -> w 此时，我们的逻辑检查该字符之前是否存在。自出现以来，它从索引“1”开始计数。这完全搞乱了整个计数。因此，我们需要确保从映射中获取的下一个索引始终大于计数的起点(即，仅当字符出现在 startingIndexOfLongestSubstring 之前时，才从映射中选择该字符)。

希望我已经回答了代码中的所有行，主要是如果解释可以理解的话。