3. Longest Substring Without Repeating Characters

解法一

思路

Brute Force 解法：For each character, find the longest non-duplicate substring starting from the character. As long as there is a duplicate character, move to next iteration. Update the maximum length in each iteration. Check duplicate by HashSet.

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length;
        int max = 0;
        int i = 0;
        HashSet<Integer> set;
        Loop:
        while (i < s.length()) {
            length = 0;
            set = new HashSet<>();
            int j = i;
            while (j < s.length() && !set.contains(s.charAt(j))) {
                    set.add(s.charAt(j));
                    j++;
                    length++;
                    max = Math.max(max, length);
            }
            i++;
        }
        return max;
    }
}

复杂度分析

• 时间复杂度
  O(n^2) since there are two while loops.
• 空间复杂度
  O(n) since we have a HashSet for detecting duplicate.

解法二

思路

Sliding windows. Set two pointers starting at the beginning of the string. Move one pointer forward as long as there is no duplicate indicating by a HashSet. Also add the character into the HashSet. If there is a character duplicates, just remove the character at i until there is no duplicate in the HashSet.

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0; int j = 0;
        HashSet<Character> set = new HashSet<>();
        int max = 0;
        int length = 0;
        while (i < s.length() && j < s.length()) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j));
                j++;
                max = Math.max(max, ++length); // j - 1
            } else {
                set.remove(set.charAt(i++));
                length--; // 可以省略，长度更新用 j - 1
            }
        }
        return max;
    }
}

复杂度分析

• 时间复杂度
  Worst case: O(2n): Consider the case: sqwjhjfee. The last character is the duplicate.
• 空间复杂度
  O(n)

Optimized Sliding Window

Store the index of characters in a HashMap, so once a dulicate appears, we can immdiately skip to the position of the character first appears.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0; int j = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int length = 0;
        while (i < s.length() && j < s.length()) {            
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            max = Math.max(max, j - i + 1);
            map.put(s.charAt(j), ++j);
        }
        return max;
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接