3. Longest Substring Without Repeating Character - Leet Code

Problem Description

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

Example 1:

• Input: s = "abcabcbb"
• Output: 3

Example 2:

• Input: s = "pwwkew"
• Output: 3

My Idea

The idea here is to utilize the Sliding Window approach. In every step we increase the window to the right. If we encounter a character that’s already a part of the current substring (window), we shorten from the left until the original instance is just outside of the window. The Window slides once over the entire string resulting in a time complexity of O(n).

My solution

# Time Complexity: O(n)
def lengthOfLongestSubstring(s:str) -> int:
    sub = set()
    l = 0
    maxLen = 0
    for r in range(0,len(s)):
        while s[r] in sub:
            sub.remove(s[l])
            l+=1
        sub.add(s[r])
        maxLen = max(maxLen,(r-l)+1)
    return maxLen