# 0003. Longest Substring Without Repeating Characters

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

## Description

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

**Example 1:**

```
**Input:** s = "abcabcbb"
**Output:** 3
**Explanation:** The answer is "abc", with the length of 3.
```

**Example 2:**

```
**Input:** s = "bbbbb"
**Output:** 1
**Explanation:** The answer is "b", with the length of 1.
```

**Example 3:**

```
**Input:** s = "pwwkew"
**Output:** 3
**Explanation:** The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
```

**Example 4:**

```
**Input:** s = ""
**Output:** 0
```

**Constraints:**

* `0 <= s.length <= 5 * 104`
* `s` consists of English letters, digits, symbols and spaces.

## AC1: Sliding window, template

A template applicale to its evolved versions.

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

        // build note/map
        int[] note = new int[256];

        // walk string
        int l = 0, r = 0, repeat = 0, lgst = 0;
        for (; r < s.length(); r++) {
            char c = s.charAt(r);
            note[c]++;
            if (note[c] > 1) repeat++; // update counter, to validate window

            // window is qualifying
            while (repeat > 0) {
                lgst = Math.max(lgst, r - l); // record current substring length
                // move window
                note[s.charAt(l)]--;
                if (note[s.charAt(l)] == 1) repeat--;
                if (l >= r) break;
                l++;
            }
        }
        // r hit the end?
        lgst = Math.max(lgst, r - l);

        // result
        return lgst;
    }
}
```

## AC2: Sliding window, regular

```cpp
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last_seen_pos(256, -1);
        int cursor = -1, max_len = 0;
        for (int i = 0; i < s.length(); i++) {
            if (last_seen_pos[s[i]] > cursor) {
                cursor = last_seen_pos[s[i]];
            }
            last_seen_pos[s[i]] = i;
            max_len = max(max_len, i - cursor);
        }
        return max_len;
    }
};
```
