LeetCode Problem #3: Longest Substring Without Repeating Characters - Explanation and Solutions in Python and JavaScript

Introduction

The Longest Substring Without Repeating Characters problem is a classic string manipulation problem frequently asked in coding interviews. It tests your understanding of sliding windows, hash maps, and string traversal. In this post, we'll break down the problem, explain the optimal approach, and provide solutions in both Python and JavaScript.

Problem Statement

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

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc", which has a length of 3.
    

Approach

The problem can be solved efficiently using the **sliding window** technique. Here's the step-by-step approach:

1. Use two pointers, left and right, to represent the current window.
2. Use a hash map (or set) to store the characters in the current window.
3. Move the right pointer to expand the window and add characters to the hash map.
4. If a repeating character is found, move the left pointer to shrink the window and remove characters from the hash map.
5. Keep track of the maximum length of the window during the process.

Solution in Python

def lengthOfLongestSubstring(s):
    char_map = {}
    left = 0
    max_length = 0

    for right in range(len(s)):
        if s[right] in char_map and char_map[s[right]] >= left:
            left = char_map[s[right]] + 1
        char_map[s[right]] = right
        max_length = max(max_length, right - left + 1)

    return max_length
        

Explanation: We use a hash map to store the last seen index of each character. If a repeating character is found, we move the left pointer to the right of the last occurrence of that character. We update the maximum length of the window during each iteration.

Solution in JavaScript

function lengthOfLongestSubstring(s) {
    const charMap = new Map();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        if (charMap.has(s[right]) && charMap.get(s[right]) >= left) {
            left = charMap.get(s[right]) + 1;
        }
        charMap.set(s[right], right);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}
        

Explanation: Similar to the Python solution, we use a hash map to store the last seen index of each character. If a repeating character is found, we move the left pointer to the right of the last occurrence of that character. We update the maximum length of the window during each iteration.

Time and Space Complexity

Time Complexity: O(n) - We traverse the string once.
Space Complexity: O(min(m, n)) - Where m is the size of the character set (e.g., ASCII or Unicode). In the worst case, the hash map stores all unique characters.

Edge Cases

• Empty string.
• All characters are the same (e.g., "aaaaa").
• String with no repeating characters (e.g., "abcdef").
• String with repeating characters at the beginning or end.

Conclusion

The Longest Substring Without Repeating Characters problem is a great way to practice the sliding window technique and hash maps. By understanding this approach, you can solve similar problems like Minimum Window Substring or Longest Substring with At Most Two Distinct Characters. Try solving it on your own and explore related problems on LeetCode!