Coders Crushby Napplied AI
Back to DSA Problems
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
Coders Crushby Napplied AI

The ultimate interview preparation platform. Master System Design, DSA, and tackle community challenges to crush your FAANG interviews.

System Design

  • All Problems
  • Easy
  • Hard

DSA

  • All Problems
  • Dynamic Programming
  • Graphs

More

  • Problems Arena
  • Growth Paths
  • AI Discovery

Coders Crush by Napplied AI - Built for engineers preparing for FAANG/MAANG interviews

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
GoogleAmazonMetaAppleMicrosoftBloombergAdobe