---
# System prepended metadata

title: Longest Substring Without Repeating Characters
tags: [data_structure_python]

---

---
tags: data_structure_python
---

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

---

**Rephrase question:**

What is the longest substring which can be formed from the input, where all characters in the substring are unique? There may be multiple substrings of the same length.

```
Input. "abcabcbb"
Output. 3
Explanation. The longest substring is of length 3. Longest substrings include "abc", "bca", and "cab".
```

```
Input. "pwwkew"
Output. 3
Explanation. The longest substring is of length 3. Longest substrings include "wke" and "kew".
```

# Solution


## Solution 1: Sliding window not optimized.

```python=
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Time complexity: O(n*k) with k = size of substring.
        # Space complexity: O(1).
        n = len(s)
        if n < 2:
            return n
        else:
            res, beg = 0, 0
            for end in range(1, n):
                while s[end] in s[beg:end]:
                    beg+=1
                res = max(res, end-beg+1)
            return res    
```

## Solution 2: Sliding window optimized (Hashmap)

```python=
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Time complexity: O(n).
        # Space complexity: O(m) with size of hashmap.
        if len(s) < 2:
            return len(s)
        else:
            hashmap = {} # {char: index}
            res, beg = 0, 0
            for end, char in enumerate(s):
                if char in hashmap and beg <= hashmap[char]:
                    beg = hashmap[char]+1            
                res = max(res, end-beg+1)
                hashmap[char] = end
            return res
```

## Solution 3: Sliding window optimized (Table)

```python=
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Time complexity: O(n).
        # Space complexity: O(256) = O(1).
        if len(s) < 2:
            return len(s)
        else:
            table = [-1]*256 # Extended ASCII table.
            res, beg = 0, 0
            for end, char in enumerate(s):
                if table[ord(char)] != -1 and beg <= table[ord(char)]:
                    beg = table[ord(char)]+1            
                res = max(res, end-beg+1)
                table[ord(char)] = end
            return res
```