DEV Community

Mahdi SHamlou | مهدی شاملو
Mahdi SHamlou | مهدی شاملو

Posted on

Mahdi Shamlou | Solving LeetCode #3: Longest Substring Without Repeating Characters — My First Attempt & My Optimal Way

#algorithms #coding #interview #leetcode

Hey everyone! Mahdi Shamlou here — continuing my LeetCode classic problems series.

After [Add Two Numbers], today we’re solving Problem #3 — Longest Substring Without Repeating Characters — another very famous interview question!

Mahdi Shamlou | مهدی شاملو

Problem Statement

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

Examples: 

Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest substring without repeating characters.

Input: s = "bbbbb"
Output: 1

Input: s = "pwwkew"
Output: 3
Explanation: "wke" (length 3)
Enter fullscreen mode Exit fullscreen mode

My first intuitive solution (Brute Force style)

This was my very first idea when I solved it:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        max_len = 0
        lists = []
        for i in range(0, len(s)):
            for z in range(i, len(s)):
                if s[z] in lists:
                    lists = []
                    break
                else:
                    lists.append(s[z])
                if max_len < len(lists):
                    max_len = len(lists)
        return max_len
Enter fullscreen mode Exit fullscreen mode

What’s wrong with this solution?

  1. Time complexity ≈ O(n³) → very slow for longer strings

  2. Using in on list is O(n) → big performance killer

My Optimal Way — Sliding Window (O(n) time)

This is the approach almost everyone expects in interviews today:

class Solution:
    def lengthOfLongestSubstring(self, s):
        my_last_seen_char_in_s = {}
        left_of_window = 0
        max_len = 0

        for right_of_window, char in enumerate(s):
            if char in my_last_seen_char_in_s and my_last_seen_char_in_s[char] >= left_of_window:
                left_of_window = my_last_seen_char_in_s[char] + 1

            my_last_seen_char_in_s[char] = right_of_window
            max_len = max(max_len, right_of_window - left_of_window + 1)

        return max_len
Enter fullscreen mode Exit fullscreen mode

Why this is beautiful:

1.Single pass → O(n) time
2.Uses dictionary for instant lookup
3.Smartly jumps the window when duplicate is found
4.Very clean and easy to explain

My repo (all solutions are here)

What about you? Which approach do you like most? Do you have any other creative solutions? Share in the comments — I read everything! 🚀

Connect with me:

🔗 LinkedIn: https://www.linkedin.com/in/mahdi-shamlou-3b52b8278

📱 Telegram: https://telegram.me/mahdi0shamlou

📸 Instagram: https://www.instagram.com/mahdi0shamlou/

Author: Mahdi Shamlou | مهدی شاملو

Top comments (0)