# 3. Longest Substring Without Repeating Characters

{% hint style="info" %}
Two methods:

1. Dynamic Programming
2. Sliding Window
   {% endhint %}

### Solution 1:

Know the longest length of first `i` chars, then the longest length of first `i+1` chars is max(`longest[i]`, longest length from `i+1` to `0`).

{% tabs %}
{% tab title="Python" %}

```python
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # edge case
        if len(s) == 0:
            return 0
        
        # initialize
        longest = 1
        
        # compute based on last element
        for i in range(1, len(s)):
            sub = []
            for j in reversed(range(0, i+1)):
                if s[j] in sub:
                    break
                else:
                    sub.append(s[j])
            longest = max(len(sub), longest)
            
        return longest
```

{% endtab %}
{% endtabs %}

Time complexity = $$O(n^2)$$ , space complexity = $$O(n)$$ .效率很低

### Solution 2:

Keep a sliding window by left and right pointers, left pointer doesn't move, right pointer moves. If s\[right] is duplicated in sliding window, s\[left] is removed from the set pf sliding window and left pointer moves one step, repeat this step until s\[right] is not duplicated in sliding window. At the same time, record the longest length of the sliding window.

```python
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        left = 0
        window = set()
        result = 0
        for right in range(len(s)):
            while s[right] in window:
                window.remove(s[left])
                left += 1
            window.add(s[right])
            result = max(result, right-left+1)
        return result
```

Time complexity = $$O(n)$$ , space complexity = $$O(n)$$ .


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/zhong-yu-shua-dao-100-dao-le-wo-shi-fen-shui-ling/bu-chong-120-dao/untitled.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.