[LeetCode] 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 subsequenceand not a substring.

Sol: Use HashMap to store the index of each character. Record the start of the non-repeating substring and the max length of it util the current index.

public int lengthOfLongestSubstring(String s) {
    if (s == null) return 0;
    int head = 0; // Record the substring index
    int maxLength = 0;
    HashMap<Character, Integer> charIndex = new HashMap();
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (charIndex.containsKey(ch)) {
            // Two conditions here
            // 1. Find the repeat one, set the recorded head to the next index of it.
            // 2. The old index which is out of the current inspecting window. Ignore it.
            head = Math.max(head, charIndex.get(ch) + 1);
        }
        maxLength = Math.max(maxLength, i - head + 1);
        charIndex.put(ch, i);
    }

    return maxLength;
}

Result: Beat about 50% competitors.
Time Complexity: O(n)
Space Complexity: O(n)