3.md

3. Longest Substring Without Repeating Characters

Description

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.

Thinking Process

1. Use a hash table to store the most recent occurence of each character
2. Save the index（denote as k）of the most recent repeating character, the substring must start from k
3. Update k and maxLen as we scan through the array

Remark

1. Convert the indexing system to 1-based instead of 0-based to include corner case of a string with only a single character

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0;
    int lastRepeatingIndex = 0;

    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(map.containsKey(c)){
            lastRepeatingIndex = Math.max(map.get(c), lastRepeatingIndex);
        }
        maxLen = Math.max(maxLen, i - lastRepeatingIndex + 1);
        map.put(c, i + 1);
    }
    
    return maxLen;
}

Complexity

1. The string is scanned once, time complexity is O(n).
2. Space complexity is O(n) as a result of using hash table.