LeetCode Challenge: 3. Longest Substring Without Repeating Characters - JavaScript Solution 🚀

Top Interview 150

The Longest Substring Without Repeating Characters problem is a classic sliding window problem that tests your ability to efficiently manage substrings. Let’s solve LeetCode 3 step by step.

---

🚀 Problem Description

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

💡 Examples

Example 1

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

Example 2

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

Example 3

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

---

🏆 JavaScript Solution

We will use the sliding window technique to track the current substring and a Set to ensure there are no duplicate characters.

Sliding Window Implementation

var lengthOfLongestSubstring = function(s) {
    let maxLength = 0;
    let left = 0;
    const seen = new Set();

    for (let right = 0; right < s.length; right++) {
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }

        seen.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};

---

🔍 How It Works

1. Sliding Window:

   • Use two pointers (left and right) to represent the current substring.
   • The right pointer expands the window by including characters.
   • The left pointer shrinks the window to eliminate duplicate characters.

2. Set for Uniqueness:

   • Use a Set to store characters in the current substring.
   • If a duplicate is found, remove characters from the left until the duplicate is removed.

3. Update Maximum Length:

   • Calculate the substring length as right - left + 1 and update maxLength.

---

🔑 Complexity Analysis

• Time Complexity: O(n), where n is the length of the string.

  • Each character is added and removed from the Set at most once.

• Space Complexity: O(k), where k is the size of the character set (e.g., 26 for lowercase English letters).

---

📋 Dry Run

Input: s = "abcabcbb"

Output: 3

---

Alternative: Optimized Sliding Window with Hash Map
Instead of using a Set, a hash map can track the last index of each character.

---

Optimized Implementation

var lengthOfLongestSubstring = function(s) {
    let maxLength = 0;
    let left = 0;
    const charIndexMap = {};

    for (let right = 0; right < s.length; right++) {
        if (charIndexMap[s[right]] !== undefined && charIndexMap[s[right]] >= left) {
            left = charIndexMap[s[right]] + 1;
        }

        charIndexMap[s[right]] = right;
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};

---

🔑 Complexity Analysis (Optimized Version)

• Time Complexity: O(n), as each character is processed once.
• Space Complexity: O(k), where k is the size of the character set.

---

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Minimum Size Subarray Sum - JavaScript Solution

Which sliding window implementation do you prefer? Let’s discuss below! 🚀

---

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!