# 3. Longest Substring Without Repeating Characters

## problem description

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

### example

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

## algorithm thought

第三遍做这个题了，首先看到题目就觉得应该用快慢指针做。定义一个快指针，每次让快指针先走，快指针每走一步记录走过的字符。如果出现快指针走过的字符之前出现过一次，就让慢指针走。慢指针每走一步，擦除一个记录，如果擦出的刚好是快指针当前的字符，慢指针停止，又轮到快指针走。快指针每走一步计算一次快慢指针之差，最后返回最大的差值就行。

然而我看我第二次做的记录，发现第二次的方法更好(大概律是看discuss的)，每次不是记录出现的次数，而是记录字符的位置，每次碰到重复的可以直接跳转到相应的位置，而不是一次次慢慢走。

## code

```cpp
//快慢指针
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0)
            return 0;
        int head=1,last=0,res=1;
        vector<int> pos(256,0);
        pos[s[last]]++;
        while(head<s.size()){
            if(++pos[s[head++]]==2){
                while(true){
                    if(--pos[s[last++]]==1)
                        break;
                }
            }
            res=max(res,head-last);
        }
        return res;
    }
};

//直接记录位置
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left=-1;
        vector<int> pos(256,-1);
        int res=0;
        for(int i=0;i<s.size();++i){
            if(pos[s[i]]>left){
                left=pos[s[i]];
            }
            pos[s[i]]=i;
            res=max(res,i-left);
        }
        return res;
    }
};
```

## algorithm analysis

首先分析快慢指针，快慢指针最坏情况是所有字符一样，最好情况是所有字符都不同。在输入为n的情况下，最坏情况需要运行2n次，最好情况需要运行n次。最好最坏都是O(n)的时间复杂度。

记录位置的方法:只有一个循环，不管什么清况都是运行n次，时间复杂度是O(n)。

综合来看还是第二种方法更好


---

# 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://kongchengzhuge.gitbook.io/leetcode/3.-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.