# Longest Substring Without Repeating Characters

## Question

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

**Example**

For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

**Challenge**

O(n) time

**Tags**

String Two Pointers Hash Table

**Related Problems**

Medium Longest Substring with At Most K Distinct Characters

## Analysis

同样可以用窗口类型Two Pointers来解决，从两重for循环中优化算法，外层指针依次遍历，内层指针根据条件决定是否需要前进。

这样一类问题要熟练掌握思路：

```java
for (i = 0; i < n; i++) {
    while (j < n) {
        if (满足条件)
            j++
            更行j状态
        else (不满足条件)
            break
    }
    更新i状态
}
```

## Solution

```java
public class Solution {
    /**
     * @param s: a string
     * @return: an integer
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashSet<Character> hs = new HashSet<Character>();
        int ans = 0;

        int i = 0;
        int j = 0;
        for (i = 0; i < s.length(); i++) {
            while (j < s.length() && !hs.contains(s.charAt(j))) {
                hs.add(s.charAt(j));
                ans = Math.max(ans, j - i + 1);
                j++;
            }

            hs.remove(s.charAt(i));
        }
        return ans;
    }
}
```

### LeetCode official: HashMap + Two Pointers

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.

**Complexity Analysis**

* Time complexity :O(n)O(n). Indexjjwill iteratenntimes.
* Space complexity (HashMap) :O(min(m,n))O(min(m,n)). Same as the previous approach.

```java
public class Solution {
    public 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;
    }
}
```

## Reference

* [Jiuzhang](http://www.jiuzhang.com/solutions/longest-substring-without-repeating-characters/)