Finding the longest substring without repeating characters: A super-simplified explanation

Solutions in Python

📌 The problem statement

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

Example:

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

The solution 💡

Let’s think of a straightforward approach first as we did with the maximum subarray sum.

1. We can create all substrings without repeating characters and then find the one that has the longest length.
2. For the above example, we have substrings without repeating characters as follows: a, ab, abc, b, bc, bca, c, ca, cab. You can manually check.
3. Now, you can verify that the longest substring is of length 3, which is the required answer.

Converting our logic to code

• We have a string. Just like with an array, we have to travel through each item in the string. So there will be a for loop.
• We need to create substrings as we loop and break the substring when we reach a repeating character.
• We can use a variable called maxLen to keep track of the length of this substring and update it if it is greater than the current maxLen.

Here’s the python implementation of the same:

I recommend you do a dry run for yourself with one of the examples to properly visualize how it is working. You will notice that one for loop is actually redundant here and can be removed.

How to optimize?

Two for loops is always a bad sign. The time complexity is O(n^2). The next question you should ask yourself is if you can do it using one loop itself.

• First, we can put a condition for edge cases. If the entire string is unique, we can see that the required answer is the length of the string itself. This also covers the empty string scenario. We can find the same using the set() function in python which returns the set of only unique elements of the datatype, be it an array or string. Notice how it is used in the code. It comes in handy at many places.
• As we travel through the string in the loop, there are only two possibilities, the given character in the string is either part of the longest substring or it is not. How do we determine that? If that character already appeared in the substring we are building, we break it there and store the length till that point and start a new substring from that character.

Do read the code comments and perform a dry run with an example.

Can we do even better?

Logically thinking, it can be hard to come up with another efficient solution by yourself. However, with some subtle hints and background knowledge, perhaps we can pick up something.

Here’s a well-detailed blog of what need to learn to solve a lot of arrays and strings problems efficiently, which otherwise look difficult.

How to Solve Sliding Window Problems

So, it’s gonna take some time to actually get a grasp of this concept. Don’t worry if you find it difficult to grasp. Let us see how we can build this logic for our problem.

I will write a separate blog exploring sliding window technique and how to simplify it as much as possible, on top of the above blog. We will also solve a bunch of problems related to the same. To be honest, even I am confused and want to get a deeper understanding of this technique.

In the meantime, you can explore solving this leetcode problem with the approach discussed in this blog. I have covered the Python solution. See, if you can come with the Javascript code.

Longest Substring Without Repeating Characters - LeetCode