3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

My Solutions:

用hashset确保set里没有重复字母，l 是sliding window 的start，r 是移动的end

public int lengthOfLongestSubstring(String s) {
    int len = s.length(), l = 0, r = 0, ans = 0;
    Set<Character> set = new HashSet<>();
    while (l < len && r < len) {
        if (!set.contains(s.charAt(r))) { // 如果window末尾的字母没有出现过
            set.add(s.charAt(r++)); // 先移动r，增加window的长度
            ans = Math.max(ans, r - l); // 计算长度最大值
        } else { // 如果当前字母已经出现过，需要移动窗口
            set.remove(s.charAt(l++)); // 把当前在l位置的字母去除，并且l++
        }
    }
    return ans;
}

可以用hashmap进一步优化，map里记录每个字母出现的最后一个index。窗口不需要每次只移动一个位置，直接把窗口移动到最后的位置。

• Time complexity: O(n)

• Space complexity: O(n)

public int lengthOfLongestSubstring(String s) {
    int len = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>(); 
    for (int l = 0, r = 0; r < len; r++) {
        char c = s.charAt(r);
        if (map.containsKey(c)) {
            // l needs to be moved to the position after the last occurring position of c
            // 或者现在l所在的位置。这样保证了window总是向右移动
            l = Math.max(map.get(c) + 1, l);
        }
        ans = Math.max(ans, r - l + 1);
        map.put(c, r); // map里记录的是c最后出现的index，此时的index=r
    }
    return ans;     
}