Longest Substring Without Repeating Characters Leetcode 3 [Python]

Are you ready to tackle another exciting LeetCode problem?

We'll be diving into "Longest Substring Without Repeating Characters," a classic problem that will challenge your problem-solving skills.

In this guide, we'll explore the problem, provide a solution in Python, and explain the reasoning behind our approach.

So, let's get started!

Problem Overview

The task at hand is quite simple but intriguing.

Given a string s, your goal is to find the length of the longest substring that does not contain any repeating characters.

For example, in the string "abcabcbb," the longest substring without repeating characters is "abc," which has a length of 3. Let's delve into the problem with an example:

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. It's crucial to note that the answer must be a substring; a subsequence, such as "pwke," is not considered a valid solution.

Now, let's examine this problem further and understand the constraints that we need to work within.

Understanding Constraints

Before we dive into the solution, it's important to understand the constraints provided:

The length of the input string s can range from 0 to 50,000.
The characters in the string s consist of English letters, digits, symbols, and spaces.

With these constraints in mind, we can develop an efficient solution to find the longest substring without repeating characters.

Efficient Python Code Solution

We will present an efficient Python solution to solve this problem using a technique called the sliding window.

This approach allows us to keep track of the current valid substring without repeating characters.

Here's the Python code solution:

View on GitHub ➹

def lengthOfLongestSubstring(s: str) -&gt; int:
    charSet = set()
    l = 0
    res = 0

    for r in range(len(s)):
        while s[r] in charSet:
            charSet.remove(s[l])
            l += 1
        charSet.add(s[r])
        res = max(res, r - l + 1)
    return res

Now, let's break down how this code works and why it's efficient.

How the Code Works

We begin by initializing an empty set called charSet to keep track of the characters in our current window.
We also set two pointers, l and r, to mark the left and right boundaries of our sliding window. l starts at 0, and r will iterate through the string s.
As we move the right pointer r through the string, we check if the character at s[r] is already in our charSet.

If it is, that means we've encountered a duplicate character in our current window.
4. When we find a duplicate, we need to shrink our window by moving the left pointer l to the right while removing characters from the charSet until the duplicate character is no longer in the set.
5. As we remove characters from the left and add characters to the right, we keep track of the maximum length of the valid substring in the res variable.
6. Finally, we return the value stored in res as the length of the longest substring without repeating characters.

Efficiency

The sliding window technique allows us to efficiently solve this problem in O(n) time complexity, where n is the length of the input string s.

We iterate through the string once, and each character is either added or removed from the charSet just once.

This makes the code very efficient.

The memory complexity is also O(n) because, in the worst case, we may need to store all characters from the input string in the charSet.

However, the space usage is optimized for the given constraints.

Reasoning Behind Our Approach

The key to this efficient solution is the sliding window technique.

By maintaining a set of characters within the current window, we can instantly detect duplicate characters.

When we encounter a duplicate, we shrink the window by moving the left pointer, ensuring that we always have a valid substring without repeating characters.

This approach allows us to find the length of the longest such substring efficiently.

Conclusion

In this guide, we explored the Longest Substring Without Repeating Characters problem on LeetCode.

We provided a Python solution that utilizes the sliding window technique to find the length of the longest substring without repeating characters efficiently.

Understanding the constraints and applying this technique allows us to solve the problem in O(n) time complexity.

If you have any questions, suggestions, or would like to share your own solution, please feel free to comment below.

LeetCode problems are a great way to enhance your problem-solving skills, so keep practicing and enjoy your coding journey!

Link to the original question on LeetCode