> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/sliding-window/0003.-longest-substring-without-repeating-characters.md).

# 0003. Longest Substring Without Repeating Characters

Medium  |  String + Two Pointer  |  36 ms (99.77%),  13.7 MB (73.48%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0003-longest-substring-without-repeating-characters)

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

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

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

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

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.

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
Instead of checking each possible substring in the input string:&#x20;

{% hint style="info" %}
We could use **two pointers** to form a **sliding window** to get the longest substring.
{% endhint %}

Regarding the repeating characters, we could use the **hash table** (dict or set in Python) to record each character in the current sliding window.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # (base case)
        if not s: return 0
        
        # ==================================================
        #  Hash Table + Sliding Window (Two Pointer)       =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        table = set()
        slowP, fastP = 0, 0
        ans = float('-inf')
        
        while fastP < len(s):
            if s[fastP] not in table:
                table.add(s[fastP])
                fastP += 1
                ans = max(ans, fastP - slowP)
                
            else:
                table.remove(s[slowP])
                slowP += 1
                
        return ans

```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n)
     */
     
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> hashTable = new HashMap<>();
        int ans = 0, slowP = 0, fastP = 0;
        
        int length = s.length();
        if( length == 0 ){ return 0; }
        
        while( fastP < length ){
            char curChar = s.charAt( fastP );
            
            if( !hashTable.containsKey( curChar ) ){
                hashTable.put( curChar, fastP );
                fastP++;
                ans = Math.max( ans, fastP-slowP );
                
            } else {
                curChar = s.charAt( slowP );
                hashTable.remove( curChar );
                slowP++;
            }
        }
        
        return ans;
    }
}

```

{% endtab %}
{% endtabs %}