3. Longest Substring Without Repeating Characters

Link

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

Example 1:

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

Example 2:

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

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

Solution

Note: In a HashMap, there is no duplicated key

1. Using hashMap to record the character and its last index

2. traversal the string, if the character appears before and it's index is greater than Start index

   1. It might smaller than start index, if the start index has been updated before

      ex. abba,

   The start index is updated to 2 before because b is duplicated.

   then the "a" duplicated doesn't impact start index, since the first a index is less than Start

3. Update the start index

 public int lengthOfLongestSubstring(String s) {
        int ret = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for(int end = 0, start = 0; end < s.length(); end++){
            
            if(map.containsKey(s.charAt(end))){
                //duplicate, let start index move to the one after the duplicated element
                start = Math.max(start, map.get(s.charAt(end))+1);
            }
            map.put(s.charAt(end), end);
            ret = Math.max(ret, end - start + 1);
        }
        return ret;
    }