🔗 LeetCode🔗 Neetcode

Longest Substring Without Repeating Characters

Mediumsliding windowAmazonMetaGoogleBloomberg

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

Examples

Input:s = "abcabcbb"
Output:3
Explanation:The answer is "abc", with the length of 3.
Input:s = "bbbbb"
Output:1
Explanation:The answer is "b", with the length of 1.
Input:s = "pwwkew"
Output:3
Explanation:The answer is "wke", with the length of 3.

Constraints

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

💡 Hints

Hint 1

Use a sliding window with a Set to track characters in the current window.

Hint 2

Expand right. If duplicate found, shrink from left until no duplicate.

Hint 3

Track the maximum window size seen.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear
Algorithmic Approach

Sliding window with a Set. Expand right, shrink left on duplicates, track max window size.

Time ComplexityO(n)
Why:

Sliding window with two pointers scans each character at most twice (once upon enter, once upon exit).

Space ComplexityO(min(n, m))
Why:

A hash set or map stores at most min(n, m) characters, bounded by the character set size m.

Big-O Growth CurveLinear (O(N))
Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

NetworkingPacket deduplication

Finding the longest unique sequence of packet IDs in a data stream before a repeat occurs.

🔍 Dry Run

Solution⏱ O(n) | 💾 O(min(n, m))
Line2
charSet={}set
left=0number
maxLen=0number

Initialize: empty Set, left=0, maxLen=0. Trace 'abcabcbb'.