> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/sliding-window/dynamic-window/longest-substring-without-repeating-characters.md).

# Longest Substring Without Repeating Characters

<https://leetcode.com/problems/longest-substring-without-repeating-characters/description/>

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

## Thoughts

问连续子数组最长能有多少通常用滑动窗口。对每个底为r的连续子数组看l要靠到多近才能满足题意。当r往前移时，l只能继续往前移才能满足新条件。

## Code

```
/*
 * @lc app=leetcode id=3 lang=cpp
 *
 * [3] Longest Substring Without Repeating Characters
 *
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
 *
 * algorithms
 * Medium (28.77%)
 * Likes:    6248
 * Dislikes: 355
 * Total Accepted:    1.1M
 * Total Submissions: 3.7M
 * Testcase Example:  '"abcabcbb"'
 *
 * 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.
 * 
 * 
 * 
 * 
 * 
 */
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0, r = 0, res = 0;
        unordered_map<char, int> count;
        while (r < s.size()) {
            if (!count.count(s[r])) count[s[r]] = 0;
            ++count[s[r]];
            while (count[s[r]] > 1) {
                --count[s[l]];
                ++l;
            }
            res = max(res, r - l + 1);
            ++r;
        } 
        return res;
    }
};


```

## Analysis

Errors:

1. 没有找nums\[i]在滑动窗口中出现的最后位置。

时间复杂度O(n)

## Ver.2

实际上我们只关心三个东西，i，pos和与nums\[i]在i前出现所在的最后位置。因此可以用一个map记录下当i++时每个nums\[i]的最后出现位置。

```
 public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
```