> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/string/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/>

## 题目描述

```
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.
```

## 代码

### Approach 1: Sliding Window

**Complexity Analysis**

* Time complexity : `O(2n)`
* Space complexity : `O(min(m, n))`

```java
class Solution {
  public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int ans = 0, i = 0, j = 0;
    while (i < n && j < n) {
      if (!set.contains(s.charAt(j))) {
        set.add(s.charAt(j++));
        ans = Math.max(ans, j - i);
      } else {
        set.remove(s.charAt(i++));
      }
    }

    return ans;
  }
}
```

### Approach 2: Sliding Window Optimized

map: Character => Index

conatians character => update `i`

```java
class Solution {
  public int lengthOfLongestSubstring(String s) {
    int n = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>();

    for (int j = 0, i = 0; j < n; j++) {
      if (map.containsKey(s.charAt(j))) {
        i = Math.max(map.get(s.charAt(j)) + 1, i);
      }
      ans = Math.max(ans, j - i + 1);
      map.put(s.charAt(j), j); 
    }

    return ans;
  }
}
```

用 `int[128]` 代替 map: Character => index

```java
class Solution {
  public int lengthOfLongestSubstring(String s) {
    int n = s.length(), ans = 0;
    int[] index = new int[128];
    for (int j = 0, i = 0; j < n; j++) { abbcde
      i = Math.max(index[s.charAt(j)], i);
      ans = Math.max(ans, j - i + 1);
      index[s.charAt(j)] = j + 1; // 为什么 j+1 => 当遇到i元素去重后, 取下一位
    }

    return ans;
  }
}
```

### Approach 3: Brute Force

**Intuition**

Check all the substring one by one to see if it has no duplicate character.

**Complexity**

* Time complexity: O(n^3)
* Space complexity: O(min(n,m)), The size of the Set is upper bounded by the size of the string *n* and the size of the charset/alphabet *m*.

```java
class Solution {
    public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int ans = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; i <= n; j++) {
        if (allUnique(s, i, j)) {
          ans = Math.max(ans, j - i);
        }
      }
    }

    return ans;
  }

  public boolean allUnique(String s, int start, int end) {
    Set<Character> set = new HashSet<>();
    for (int i = start; i < end; i++) {
      Character ch = s.charAt(i);
      if (set.contains(ch)) return false;
      set.add(ch);
    }
    return true;
  }

}
```