java - 函数在某些情况下可以工作，但当最长子字符串 "reuses"是一个字符时会失败

Question

我有一个名为 lengthOfLongestSubstring 的函数，它的工作是找到没有任何重复字符的最长子字符串。在大多数情况下，它可以工作，但是当它获得像“dvdf”这样的输入时，它会打印出 2(而不是 3)，并在应该是 [d, vdf] 时给出 [dv, df]。

因此，我首先检查字符串并查看是否有任何唯一字符。如果有，我将其附加到 ans 变量中。 (我认为这是需要修复的部分)。如果有重复，我将其存储在子字符串链表中，并将 ans 变量重置为重复字符串。

遍历整个字符串后，我找到最长的子字符串并返回其长度。

public static int lengthOfLongestSubstring(String s) {    
    String ans = "";
    int len = 0;
    LinkedList<String> substrings = new LinkedList<String>(); 
    for (int i = 0; i < s.length(); i++) {
      if (!ans.contains("" + s.charAt(i))) {
        ans += s.charAt(i);
      } else {
        substrings.add(ans);
        ans = "" + s.charAt(i);
      }
    }

    substrings.add(ans); // add last seen substring into the linked list

    for (int i = 0; i < substrings.size(); i++) {
      if (substrings.get(i).length() >= len)
        len = substrings.get(i).length();
    }

    System.out.println(Arrays.toString(substrings.toArray()));

    return len;


}

以下是一些测试结果:

//correct
lengthOfLongestSubstring("abcabcbb") -> 3 ( [abc, abc, b, b]) 

lengthOfLongestSubstring("pwwkew") -> 3 ([pw, wke, w]).

lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, ABEF]) 

// wrong
System.out.println(lengthOfLongestSubstring("acadf")); -> 3, ([ac, adf]) *should be 4, with the linked list being [a, cadf]

有什么建议可以解决这个问题吗？我必须重做所有逻辑吗？

谢谢!

Answer 1

您的代码错误地假设当您找到重复字符时，下一个候选子字符串从重复字符开始。这不是真的，它是在原始角色之后开始的。

示例:如果字符串为“abcXdefXghiXjkl”，则有3个候选子字符串:“abcXdef”、“defXghi”和“ghiXjkl”。

如您所见，候选子字符串在重复字符之前结束，并在重复字符之后开始(以及字符串的开头和结尾)。

因此，当您找到重复字符时，需要该字符的前一个实例的位置来确定下一个候选子字符串的开始位置。

处理这个问题的最简单方法是构建一个角色到最后看到的位置的Map。这也比不断执行子字符串搜索来检查重复字符(就像问题代码和其他答案所做的那样)执行得更快。

类似这样的事情:

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charPos = new HashMap<>();
    List<String> candidates = new ArrayList<>();
    int start = 0, maxLen = 0;
    for (int idx = 0; idx < s.length(); idx++) {
        char ch = s.charAt(idx);
        Integer preIdx = charPos.get(ch);
        if (preIdx != null && preIdx >= start) { // found repeat
            if (idx - start > maxLen) {
                candidates.clear();
                maxLen = idx - start;
            }
            if (idx - start == maxLen)
                candidates.add(s.substring(start, idx));
            start = preIdx + 1;
        }
        charPos.put(ch, idx);
    }
    if (s.length() - start > maxLen)
        maxLen = s.length() - start;
    if (s.length() - start == maxLen)
        candidates.add(s.substring(start));
    System.out.print(candidates + ": ");
    return maxLen;
}

candidates 仅用于调试目的，并且不是必需的，因此没有它，代码会更简单:

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charPos = new HashMap<>();
    int start = 0, maxLen = 0;
    for (int idx = 0; idx < s.length(); idx++) {
        char ch = s.charAt(idx);
        Integer preIdx = charPos.get(ch);
        if (preIdx != null && preIdx >= start) { // found repeat
            if (idx - start > maxLen)
                maxLen = idx - start;
            start = preIdx + 1;
        }
        charPos.put(ch, idx);
    }
    return Math.max(maxLen, s.length() - start);
}

测试

System.out.println(lengthOfLongestSubstring(""));
System.out.println(lengthOfLongestSubstring("x"));
System.out.println(lengthOfLongestSubstring("xx"));
System.out.println(lengthOfLongestSubstring("xxx"));
System.out.println(lengthOfLongestSubstring("abcXdefXghiXjkl"));
System.out.println(lengthOfLongestSubstring("abcabcbb"));
System.out.println(lengthOfLongestSubstring("pwwkew"));
System.out.println(lengthOfLongestSubstring("ABDEFGABEF"));

输出(带有候选列表)

[]: 0
[x]: 1
[x, x]: 1
[x, x, x]: 1
[abcXdef, defXghi, ghiXjkl]: 7
[abc, bca, cab, abc]: 3
[wke, kew]: 3
[ABDEFG, BDEFGA, DEFGAB]: 6