Longest Substring Without Repeating Characters – LeetCode 3 Solution

📌 Introduction

String manipulation problems are extremely common in **coding interviews**, and one of the most frequently asked problems is “Longest Substring Without Repeating Characters” (LeetCode #3). This problem is widely used by top tech companies such as **Google, Amazon, Microsoft, and Facebook (Meta)** to test a candidate’s ability to handle strings efficiently.

In this post, we will discuss two approaches: a **brute-force method** (which is inefficient) and an **optimized Sliding Window approach** that solves the problem in O(n) time complexity. If you are preparing for **FAANG interviews** or competitive programming, this problem is a must-know!

📝 Problem Statement

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

🔹 Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The longest substring is "abc", with a length of 3.

🔹 Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The longest substring is "b", with a length of 1.

🔹 Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The longest substring is "wke", with a length of 3.

❌ Brute Force Solution (O(n²))

The brute force approach generates all substrings and checks for duplicates. This method is inefficient for large input sizes.

🔹 Python Code:

def length_of_longest_substring(s):
    max_length = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            max_length = max(max_length, j - i + 1)
    return max_length

🔴 Time Complexity: O(n²) – Too slow for large input strings.

✅ Optimized Sliding Window Approach (O(n))

To efficiently solve this problem, we use the **Sliding Window Technique**:

• We maintain two pointers: left and right.
• We use a hash set to track unique characters in the window.
• If a duplicate character appears, move the left pointer until uniqueness is restored.
• Keep track of the **maximum substring length**.

🔹 Python Code:

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 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_length = max(max_length, right - left + 1)

    return max_length

✅ Time Complexity: O(n), since each character is processed at most twice.

📊 Dry Run Example

🔹 Input: s = "pwwkew"

✅ Final Output: 3