函数在某些情况下工作，但在最长子字符串"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

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])