Finding the Longest Substring Without Repeating Characters in Python

When working with strings, one common problem is finding the length of the longest substring without repeating characters. In this post, we’ll walk through a solution to this problem using Python.

Problem Description

Given a string, we need to find the length of the longest substring that does not contain any repeating characters.

Approach

To solve this problem efficiently, we can use the Sliding Window technique along with a HashSet to keep track of characters that have already been seen in the current window. Here’s the step-by-step approach:

1. Initialize Pointers: Start with two pointers, left and right, both initially pointing to the beginning of the string.
2. Use a Set: Use a set to store characters in the current window.
3. Expand the Window: Move the right pointer to expand the window by adding characters one by one to the set.
4. Shrink the Window: If a character is already in the set (meaning it’s a duplicate), move the left pointer to the right until the duplicate character is removed from the set.
5. Track Maximum Length: Keep track of the maximum length of the substring found during the process.

Python Implementation

def length_of_longest_substring(s: str) -> int:
    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

Explanation

• Set Operations: The set helps quickly check for duplicates and remove characters from the current substring when necessary.
• Time Complexity: This solution runs in O(n) time, where n is the length of the string. This is because both the left and right pointers will traverse the string only once.
• Space Complexity: The space complexity is O(min(n, m)), where n is the length of the string, and m is the size of the character set.

Test Cases

Let’s validate the function using the provided test cases:

# Test Case 1
assert length_of_longest_substring("abcabcbb") == 3  # Output: 3

# Test Case 2
assert length_of_longest_substring("bbbbb") == 1  # Output: 1

# Test Case 3
assert length_of_longest_substring("pwwkew") == 3  # Output: 3

# Test Case 4
assert length_of_longest_substring("aab") == 2  # Output: 2

# Test Case 5
assert length_of_longest_substring("dvdf") == 3  # Output: 3

Conclusion

This approach effectively handles finding the longest substring without repeating characters by using a sliding window and a set. It’s an optimal solution that performs well even for long strings.

Feel free to try this function with your test cases and see how it works. Understanding and implementing this solution is a great way to enhance your problem-solving skills in Python.