Hash Set + 双指针，其实又花了不少的时间重新理解了一下优化方法……却是很久没刷题了。

# Question

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

## En

In this case, using a hash set to store the substring of the string is a better choice since the look up time for hash set is $O(1)$.

The approach here is to use sliding window to solve the problem. For a string/array, which starting indices is $i$, and end indices is $j$. Initially, $j = i$. Then keep adding the element on $j$ into hash set, and moving the $j$ to the right until the element exists in the hash set. At this point, the length $j-i$ becomes to local maximum, therefore $i$ needs to be moved to right, and the element needs to be dropped.

### Optimized Method

Instead of using hash set, hash map or primitive type table(if charset is known and relative small) is used in the optimized method.

Save the index of next index of current index in the map. During each iteration, check whether the current value on index $j$ has already been saved in container. If so, which means all the elements to the index of that value contains repeated value, and therefore do not need to be considered anymore.

Consider the string abcade, the longest substring without repeated value is bcade. For the first a, the map stores next index of a, which is 1. When the iteration hits second a, it draws out the value of index stored on a, and starts from there. If there is any repeated value, this algorithm does the same thing by skipping several values and therefore save time.

# Complexity Analysis

• Time Complexity： $O(2n)=O(n)$, in the worst case, all the elements need to be iterated twice by $i$ and $j$
• Space Complexity: $O(min(m, n))$, where $m$ is the size of charset/slphabet, and $n$ is the size of the string.

Solution