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 consists of English letters, digits, symbols and spaces.

Approach 1 Sliding Window

### Intuition

- Given a substring with a fixed end index in the string, maintain a HashMap to record the frequency of each character in the current substring. If any character occurs more than once, drop the leftmost characters until there are no duplicate characters.

**Algorithm**

- The naive approach is very straightforward. But it is too slow. So how can we optimize it?

- In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring sijs_{ij}s ij

- By using HashSet as a sliding window, checking if a character in the current can be done in O(1)O(1)O(1).

import java.util.*;public class Solution {public static void main(String[] args){System.out.println("lengthOfLongestSubstring "+ lengthOfLongestSubstring("abcabcbb"));}public int lengthOfLongestSubstring(String s) {Map<Character, Integer> chars = new HashMap();int left = 0;int right = 0;int res = 0;while (right < s.length()) {char r = s.charAt(right);chars.put(r, chars.getOrDefault(r,0) + 1);while (chars.get(r) > 1) {char l = s.charAt(left);chars.put(l, chars.get(l) - 1);left++;}res = Math.max(res, right - left + 1);right++;}return res;}}

Approach 2 Sliding WindowOptimized

### Intuition

- The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

import java.util.*;public class Solution {public static void main(String[] args){System.out.println("lengthOfLongestSubstring "+ lengthOfLongestSubstring("abcabcbb"));}public static int lengthOfLongestSubstring(String s) {int n = s.length(), ans = 0;Map<Character, Integer> map = new HashMap<>(); // current index of character// try to extend the range [i, j]for (int j = 0, i = 0; j < n; j++) {if (map.containsKey(s.charAt(j))) {i = Math.max(map.get(s.charAt(j)), i);}ans = Math.max(ans, j - i + 1);map.put(s.charAt(j), j + 1);}return ans;}}