Longest Substring Without Repeating Characters - LeetCode(Medium) - Sliding Window Technique!

Longest Substring Without Repeating Characters - LeetCode(Medium) - Sliding Window Technique!

Hey all! I am solving a LeetCode medium problem today! Let's get right into it.

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

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

So while solving this first I thought this needed a hash map to solve it. Because what problem can't be solved with a hash map! So I was thinking in terms of that. But couldn't figure out a way to cover a lot of edge cases that came with the first algorithm. Long story short, I was looping through the characters tracking the longest substring and when I saw a repeated character I was reinitializing the substring to start from that point itself(which is where I got it wrong).

Not long after this, I realized that this was a Sliding Window problem! So I dropped hash map and wrote this algorithm instead:

int lengthOfLongestSubstring(string s) {
        int i = 0, j = 0;
        int maxim = 0;
        unordered_set<char> seen;
        while (j < s.length()) {
            if (seen.find(s[j]) != seen.end()) {
                seen.erase(seen.find(s[i]));
                i++;
            } else {
                seen.insert(s[j]);
                if (seen.size() > maxim) 
                    maxim = seen.size();
                j++;
            }
        }
        return maxim;
    }

Let's go through the algorithm line by line. As this is a sliding window problem, we will define our window between two pointers which are i and j. So for example if i = 1 and j = 6 at a certain point in the program, then we have a window consisting of 6 characters.

image.png

So for this, we initialize i, j to 0. We also declare a maxim variable to store the length of the longest substring which will be our answer.

Then we declare a set called seen. This will be used to store the characters in the current window.

And now comes the main section of the algorithm! The while loop. Here's what it does. We check if j which is the pointer to the end of the sliding window or the current character is equal to the end of the string, Which means we have checked all substrings. Inside of the loop, We check if the current character(char at j) is present in the seen set or not.

If it is present we start removing charters from the window/seen from its beginning so that the character that's repeating is eventually removed from the seen set and we keep increasing i. So the window shrinks.

If the current variable is not in the seen set, we will insert the character in the seen set as we have seen it now. And we update maxim to store the maximum length of the window so far. And we increase j to the next value. The while loop repeats this until j is the end of the given string.

That's all for the while loop! At the end of the loop, we return maxim that will store the maximum length of the substring with non-repeating characters at the end of the loop.

If this didn't make sense on the first read try taking an example string like "pwwkew" and run it through the algorithm yourself with a pen and paper.

Remember on the first try I thought this one can be solved by hash map? Well, I was right! After solving the problem I checked the solution tab and I saw the last solution was using a hash map! Here's what the solution looks like:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i = 0, j = 0;
        int m = 0;
        int len = s.length();
        map<char, int> seen;
        while (j < len) {
            if (seen.find(s[j]) != seen.end()) {
                i = max(seen.find(s[j])->second, i);
            }

            m = max(m, j - i + 1);
            seen[s[j]] = j + 1;
            j++;
        }
        return m;
    }
};

The first few lines are the same. i and j for the window and m for the maximum length. len to store the length of the given string.

This time the seen variable is actually a map of char and int storing the characters we have seen so far and their index + 1. Inside the while loop, if the current character at j is in seen we shift i to the index of the repeating character + 1 so index + 1. And for every iteration, we keep updating m to store the longest length. and store the current character and its index + 1 in the seen map and obviously increment j to keep the loop growing(increasing the length of the window). At the end of the loop, we return m which at the end of the loop will store the largest substring with non-repeating character's length.

That's it! Told you, hash map is the way to go!

See you in the next article!