3. Longest Substring Without Repeating Characters

Question

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

Example 1:

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

Example 2:

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

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Approach

1. Use a map to record each character index;
2. Loop the string, once they is a repetition, calculate the non-repeat string length by using current index minus last repeat position;
3. The last repeat position left in the below, should be updated each time you got a repeat, and it should be max of itself and or last repeat position, because abba in such condition, we update left to index 2, but for the last a, the last repeat position is 0, and we cannot include it and reset left back to index 0.
4. In other condition, we keep moving the index and calculate result.

Code

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