MediumLeetCode #3Sliding Window

Longest Substring Without Repeating Characters

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

Constraints

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

Examples

Input: s = "abcabcbb"

Output: 3

The answer is "abc", with the length of 3.

Solution

Approach

Use sliding window with a hash set or map. Expand right, and when duplicate found, shrink from left until no duplicates.

def lengthOfLongestSubstring(s):
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

Complexity

Time:O(n)

Space:O(min(m,n))

Hints

1.Use a sliding window
2.Track characters in current window with a set
3.Shrink window when duplicate found

Asked at

Google