Introduction

In this blog post, we will explore how to solve the LeetCode problem "3" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a string s, find the length of the longest substring without duplicate characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. Constraints: 0 <= s.length <= 5 * 104 s consists of English letters, digits, symbols and spaces.

Explanation

Here's the breakdown of the solution:

• Sliding Window: Utilize a sliding window approach to efficiently scan the string. The window expands to include new characters and contracts when a duplicate is encountered.
• Character Tracking: Employ a dictionary (hash map) to keep track of the characters currently within the sliding window and their most recent index. This allows for O(1) lookup to detect duplicates.

• Maximum Length Update: Continuously update the maximum substring length as the window slides, ensuring the longest substring without repeating characters is recorded.

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

• Storage Complexity: O(min(m, n)), where n is the length of the string, and m is the size of the character set (e.g., 26 for lowercase English letters, up to 128 for ASCII characters or more for Unicode). In the worst case, the hash map might store all unique characters from the string.

Code

    def length_of_longest_substring(s: str) -> int:
    """
    Finds the length of the longest substring without repeating characters.

    Args:
        s: The input string.

    Returns:
        The length of the longest substring without repeating characters.
    """
    char_index_map = {}  # Dictionary to store character and its last seen index
    start = 0  # Start of the sliding window
    max_len = 0  # Maximum length of substring without repeating characters

    for end, char in enumerate(s):
        if char in char_index_map and char_index_map[char] >= start:
            # If the character is already in the map and within the current window
            start = char_index_map[char] + 1  # Move the start of the window

        char_index_map[char] = end  # Update the character's index
        max_len = max(max_len, end - start + 1)  # Update max_len

    return max_len