> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/two-pointers/3-longest-substring-without-repeating-characters.md).

# 3 Longest Substring Without Repeating Characters

## 3. [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)

## 1. Question

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

**Examples:**

Given`"abcabcbb"`, the answer is`"abc"`, which the length is 3.

Given`"bbbbb"`, the answer is`"b"`, with the length of 1.

Given`"pwwkew"`, 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.

## 2. Implementation

**(1) Two Pointer + Hash**

```java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int maxLen = 0;
        int start = 0, end = 0;
        int count = 0;
        int[] map = new int[256];

        while (end < s.length()) {
            if (map[s.charAt(end)] > 0) {
                ++count;
            }
            ++map[s.charAt(end)];
            ++end;

            while (count > 0) {
                if (map[s.charAt(start)] > 1) {
                    --count;
                }
                --map[s.charAt(start)];
                ++start;
            }
            maxLen = Math.max(maxLen, end - start);
        }
        return maxLen;
    }
}
```

## 3. Time & Space Complexity

**Two Pointer + Hash:** 时间复杂度O(n), 空间复杂度O(1)