:orphan:

Longest Substring Without Repeating Characters
==============================================

.. highlight:: none

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

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

 

**Example 1:**

::


   Input: s = "abcabcbb"
   Output: 3
   Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

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

 

**Constraints:**

- ``0 <= s.length <= 5 * 10``\ :sup:```4```
- ``s`` consists of English letters, digits, symbols and spaces.

.. highlight:: python

Pattern
-------
Hash Table, String, Sliding Window

Solution
--------
The longest substring can start from any position in the string. So, we must
iterate through each position in the entire string. For each position, we look
right until we find a duplicate character. At each iteration, if the current
substring is longer than the longest, we update the length of the longest
substring. Once we find a duplicate character, reset the seen characters.

Code
----

.. literalinclude:: ../problems/medium/longest-substring-without-repeating-characters/longest_substring_without_repeating_characters__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from longest_substring_without_repeating_characters__approach_1 import lengthOfLongestSubstring
>>> lengthOfLongestSubstring('abcabcbb')
3
>>> lengthOfLongestSubstring('bbbbb')
1
>>> lengthOfLongestSubstring('pwwkew')
3

Complexity
----------
| :math:`n` is the length of the input string
| Time: :math:`O(n^2)` — attempt to build substring starting at each character
| Auxiliary Space: :math:`O(n)` — substring storage

.. autofunction:: longest_substring_without_repeating_characters__approach_1.lengthOfLongestSubstring