最长无重复字符的子串

Question

我正在开始使用 LeetCode，目前正在解决问题 无重复字符的最长子字符串。

给定一个字符串

s

，找到最长的不包含重复字符的子串的长度。

输入：

s = "abcabcbb"

输出：

3

说明：答案是

"abc"

，长度为

3

。

我觉得我的方法应该有效，但由于某种原因它未能通过某些测试（见下文）。有人可以帮我理解为什么吗？

public int lengthOfLongestSubstring(String s) {
        int current_max = 0; 
        HashMap<Character, Character> seen_values = new HashMap(s.length()); 
        
        int running_count = 0; 
        
        for (int i = 0; i < s.length(); i++){
            if (seen_values.containsKey(s.charAt(i))){
                running_count = 1; 
                seen_values = new HashMap(s.length());
                seen_values.put(s.charAt(i), s.charAt(i));
            } else {
                running_count++;
                if (running_count > current_max){
                    current_max = running_count; 
                }
                seen_values.put(s.charAt(i), s.charAt(i));
            }
        }
        return current_max;
    }

测试失败

输入：

"abac"

代码产生 输出

2

，但预期是

3

。

这是我能够创建的唯一失败的案例。
谁能解释一下为什么会这样？

Answer 1

您正在考虑遇到重复字符作为新子字符串的开头的情况。这是不正确的。

让我们考虑以下示例：

"abcbdef"

没有重复字符的最长子串是

"cbdef"

。

迭代从子字符串

"a"

到

"ab"

，然后到

"abc"

。这时，我们遇到了第二个角色

'b'

。我们不能将其视为新子字符串的开头，而是必须将前一个子字符串的开头移动到第一次出现的'b'

之后，即子字符串应该从

'c'

开始（

不是从第二个'b'开始）

）。

要实现此逻辑，您需要跟踪当前子字符串的起始索引（以及最大子字符串长度），而不是维护计数器。

您可以使用

HashMap

 代替 

HashSet

，因为 

@Dawood ibn Kareem 已经在评论中指出了。

迭代时，您需要将每个字符提供给集合，如果方法

add()

返回

false

，则需要执行移动子字符串起始索引的逻辑。 IE。您需要将嵌套循环中的索引移动到当前字符第一次出现的位置，并且

注意嵌套循环中遇到的每个字符都必须从集合中删除（除了当前字符）。

这种方法可以得到加强。

正如

@greybeard所建议的那样，我们通过将每个遇到的字符的索引存储在Map中，并且不仅检查下一个字符是否存在，从而跳过删除前一个和

新起始位置

之间的字符的步骤 存在，但如果与其关联的 value 大于或等于 当前起始索引。

如何实施：

public static int lengthOfLongestSubstring(String str) {
    Map<Character, Integer> charToIndex = new HashMap<>(str.length());
    int maxLength = 0;
    int start = 0;
    
    for (int end = 0; end < str.length(); end++) {
        char next = str.charAt(end);
        if (charToIndex.containsKey(next) && charToIndex.get(next) >= start) {
            start = charToIndex.get(next) + 1;
        }
        charToIndex.put(next, end);
        maxLength = Math.max(maxLength,  end - start + 1);
    }
    return maxLength;
}

main()

public static void main(String[] args) {
    System.out.println(lengthOfLongestSubstring("abcbdef"));
    System.out.println(lengthOfLongestSubstring("abac"));
}

输出：

5   // "cbdef"
3   // "bac"

Answer 2

    /*
Longest Substring Without Repeating Characters

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
*/

let str= "pwwkew";
let result = [];
let temp = '';
for (let s of str) {
    if (temp.indexOf(s) >= 0) {
        result.push(temp);
        temp = s;
    } else {
        temp+= s;
    }
}
if (temp !== '') {
    result.push(temp);    
}


console.log(result);
console.log('Sorted Array --> ', result.sort((a,b) => a.length - b.length));
console.log('Final Result ---> ', result[result.length - 1])