函数在某些情况下可以工作，但当最长的子字符串“重用”字符时会失败

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) {&nbsp; &nbsp; Map<Character, Integer> charPos = new HashMap<>();&nbsp; &nbsp; List<String> candidates = new ArrayList<>();&nbsp; &nbsp; int start = 0, maxLen = 0;&nbsp; &nbsp; for (int idx = 0; idx < s.length(); idx++) {&nbsp; &nbsp; &nbsp; &nbsp; char ch = s.charAt(idx);&nbsp; &nbsp; &nbsp; &nbsp; Integer preIdx = charPos.get(ch);&nbsp; &nbsp; &nbsp; &nbsp; if (preIdx != null && preIdx >= start) { // found repeat&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (idx - start > maxLen) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; candidates.clear();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxLen = idx - start;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (idx - start == maxLen)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; candidates.add(s.substring(start, idx));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = preIdx + 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; charPos.put(ch, idx);&nbsp; &nbsp; }&nbsp; &nbsp; if (s.length() - start > maxLen)&nbsp; &nbsp; &nbsp; &nbsp; maxLen = s.length() - start;&nbsp; &nbsp; if (s.length() - start == maxLen)&nbsp; &nbsp; &nbsp; &nbsp; candidates.add(s.substring(start));&nbsp; &nbsp; System.out.print(candidates + ": ");&nbsp; &nbsp; return maxLen;}仅candidates用于调试目的，并且不是必需的，因此如果没有它，代码会更简单一些：public static int lengthOfLongestSubstring(String s) {&nbsp; &nbsp; Map<Character, Integer> charPos = new HashMap<>();&nbsp; &nbsp; int start = 0, maxLen = 0;&nbsp; &nbsp; for (int idx = 0; idx < s.length(); idx++) {&nbsp; &nbsp; &nbsp; &nbsp; char ch = s.charAt(idx);&nbsp; &nbsp; &nbsp; &nbsp; Integer preIdx = charPos.get(ch);&nbsp; &nbsp; &nbsp; &nbsp; if (preIdx != null && preIdx >= start) { // found repeat&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (idx - start > maxLen)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxLen = idx - start;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = preIdx + 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; charPos.put(ch, idx);&nbsp; &nbsp; }&nbsp; &nbsp; 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

Answer 2

ans当找到字符匹配时，而不是设置为当前字符ans = "" + s.charAt(i);您应该将当前字符添加到当前字符的第一个匹配之后的所有字符ans = ans.substring(ans.indexOf(s.charAt(i)) + 1) + s.charAt(i);完整的方法因此变成&nbsp; &nbsp; public static int lengthOfLongestSubstring(String s) {&nbsp; &nbsp; &nbsp; &nbsp; String ans = "";&nbsp; &nbsp; &nbsp; &nbsp; int len = 0;&nbsp; &nbsp; &nbsp; &nbsp; LinkedList<String> substrings = new LinkedList<>();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < s.length(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!ans.contains("" + s.charAt(i))) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans += s.charAt(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; substrings.add(ans);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Only the below line changed&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans = ans.substring(ans.indexOf(s.charAt(i)) + 1) + s.charAt(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; substrings.add(ans); // add last seen substring into the linked list&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < substrings.size(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (substrings.get(i).length() >= len)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; len = substrings.get(i).length();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(substrings.toArray()));&nbsp; &nbsp; &nbsp; &nbsp; return len;&nbsp; &nbsp; }使用此代码，您指定的验收标准已成功通过//correctlengthOfLongestSubstring("dvdf") -> 3 ( [dv, vdf])&nbsp;lengthOfLongestSubstring("abcabcbb") -> 3 ([abc, bca, cab, abc, cb, b])&nbsp;lengthOfLongestSubstring("pwwkew") -> 3 ([pw, wke, kew]).lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, BDEFGA, DEFGAB, FGABE, GABEF])lengthOfLongestSubstring("acadf"); -> 4 ([ac, cadf])

Answer 3

创建一个嵌套的 for 循环来检查数组中的每个索引。&nbsp; &nbsp; public static int lengthOfLongestSubstring(String s) {&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; String ans = "";&nbsp; &nbsp; int len = 0;&nbsp; &nbsp; LinkedList<String> substrings = new LinkedList<String>();&nbsp; &nbsp; int k = 0;&nbsp; &nbsp; for (int i = 0; i < s.length(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; if(k == s.length()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for(k = i; k < s.length(); k++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!ans.contains("" + s.charAt(k))) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans += s.charAt(k);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; substrings.add(ans);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans = "";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; substrings.add(ans); // add last seen substring into the linked list&nbsp; &nbsp; for (int i = 0; i < substrings.size(); i++) {&nbsp; &nbsp; &nbsp; if (substrings.get(i).length() >= len)&nbsp; &nbsp; &nbsp; &nbsp; len = substrings.get(i).length();&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(Arrays.toString(substrings.toArray()));&nbsp; &nbsp; return len;}例子：lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, BDEFGA, DEFGAB, EFGAB, FGABE, GABEF])