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

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

```cpp
// int vector served as a hash table to record last occurrence index of char
int lengthOfLongestSubstring(string s) { // time: O(n); space: O(1)
    vector<int> record(128, -1); // last occurrence index
    int start = -1, res = 0;
    for (int end = 0; end < s.length(); ++end) {
        start = max(start, record[s[end]]);
        record[s[end]] = end;
        res = max(res, end - start);
    }
    return res;
}
```

```cpp
// Sliding window
int lengthOfLongestSubstring(string s) { // time: O(n); space: O(1)
    int begin = 0, end = 0, d = 0, counter = 0;
    vector<int> record(128, 0);
    while (end < s.length()) {
        if (record[s[end++]]++ > 0) {
            counter++;
        }
        while (counter > 0) {
            if (record[s[begin++]]-- > 1) {
                counter--;
            }
        }
        d = max(d, end - begin);
    }
    return d;
}
```