# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/two_pointers/longest_substring_without_repeating_characters.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.