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

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)

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)

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