What is the time complexity of LeetCode 3. Longest Substring Without Repeating Characters?

The Python solution on this page runs in O(n), where n is the length of the string.

What is the space complexity of LeetCode 3. Longest Substring Without Repeating Characters?

The Python solution on this page uses O(|\Sigma|), where \Sigma represents the character set, and the size of \Sigma is 128 auxiliary space.

Longest Substring Without Repeating Characters — LeetCode 3 Python Solution

MediumHash TableStringSliding Window

Problem: #3
Pattern: Sliding Window
Reading time: 2 min
Source: leetcode.com

The problem

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

Example

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

Python solution

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = Counter()
        ans = l = 0
        for r, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 1:
                cnt[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the string
Space	O(\|\Sigma\|), where \Sigma represents the character set, and the size of \Sigma is 128 auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 3. Longest Substring Without Repeating Characters is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

On study lists

This problem is on Blind 75, NeetCode 150, Grind 75 and Top Interview 150.

Frequently asked questions

How hard is LeetCode 3. Longest Substring Without Repeating Characters?: LeetCode 3. Longest Substring Without Repeating Characters is rated Medium on LeetCode.
What is the time complexity of LeetCode 3. Longest Substring Without Repeating Characters?: The Python solution on this page runs in O(n), where n is the length of the string.
What is the space complexity of LeetCode 3. Longest Substring Without Repeating Characters?: The Python solution on this page uses O(|\Sigma|), where \Sigma represents the character set, and the size of \Sigma is 128 auxiliary space.
What topics does LeetCode 3. Longest Substring Without Repeating Characters cover?: LeetCode 3. Longest Substring Without Repeating Characters is tagged Hash Table, String and Sliding Window on LeetCode.