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

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;}下面是一些测试结果：//correctlengthOfLongestSubstring("abcabcbb") -> 3 ( [abc, abc, b, b]) lengthOfLongestSubstring("pwwkew") -> 3 ([pw, wke, w]).lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, ABEF]) // wrongSystem.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

Answer 2

ans当找到字符匹配时，而不是设置为当前字符

ans = "" + s.charAt(i);

您应该将当前字符添加到当前字符的第一个匹配之后的所有字符

ans = ans.substring(ans.indexOf(s.charAt(i)) + 1) + s.charAt(i);

完整的方法因此变成

    public static int lengthOfLongestSubstring(String s) {

        String ans = "";

        int len = 0;

        LinkedList<String> substrings = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {

            if (!ans.contains("" + s.charAt(i))) {

                ans += s.charAt(i);

            } else {

                substrings.add(ans);

                // Only the below line changed

                ans = ans.substring(ans.indexOf(s.charAt(i)) + 1) + 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("dvdf") -> 3 ( [dv, vdf]) 

lengthOfLongestSubstring("abcabcbb") -> 3 ([abc, bca, cab, abc, cb, b]) 

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

lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, BDEFGA, DEFGAB, FGABE, GABEF])

lengthOfLongestSubstring("acadf"); -> 4 ([ac, cadf])

Answer 3

创建一个嵌套的 for 循环来检查数组中的每个索引。

    public static int lengthOfLongestSubstring(String s) {    

    String ans = "";

    int len = 0;

    LinkedList<String> substrings = new LinkedList<String>();

    int k = 0;

    for (int i = 0; i < s.length(); i++) {

        if(k == s.length()) {

            break;

        }

        for(k = i; k < s.length(); k++) {

          if (!ans.contains("" + s.charAt(k))) {

            ans += s.charAt(k);

          } else {

            substrings.add(ans);

            ans = "";

            break;

          }

        }

    }

    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;

}

例子：

lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, BDEFGA, DEFGAB, EFGAB, FGABE, GABEF])