Leetcode: Longest Substring without Repeating Characters

Instruction

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

What is Being Asked?

Write a function that loops through an input string to check for the longest subset of unique characters and return the length of it's size.

example 1: abcdd would return 4 because that's the contiguous amount of unique characters within the contents of the input string.

example 2: bbbbb would return 1 because there is a single unique character.

What Does That Look Like?

I used the Sliding Window technique with a dynamic resize to accomplish this. A Sliding Window is essentially a process for traversing a data structure to compare or modify its contents. The operation looks similar to how an accordion stretches out and releases in or perhaps the movement of a caterpillar.

Note:

Chrome uses {} when logging a Set.
Firefox uses [].

What Do I Need to Solve?

I begin with an edge case that checks if the input string is valid and return 0 if it isn't.

I chose to use a JavaScript Set object as the data structure to apply the Sliding Window technique in my solution. A Set is a collection of unique values of any type. In this case, we'll be working with typestring.

To compare and/or modify the characters of the input string from within the Sliding Window, I'll need two pointers.

I define two variables: i and j and set them each to 0.

I also define a variable: result that will store the value of the longest substring to return and initialize it to 0.

The iteration consists of a nested while loop. The i pointer drives the process. While i is less than the size of the string, each iteration will add the value of i to the Set as long as it doesn't already exist.

It then sets the result value using JavaScripts Math.max() method. This method returns the greater value of the two integers passed to it. After result is set, i increments 1 and the loop continues.

When i gets to a value already stored in the Set, j will remove the value from the window and increment 1 for the next iteration.

Once the while loops complete, the function will return the value stored in longestSubstring.

Solution

Time: O(n) where n is the number of characters in the string.
Space: O(n) where n is the length of the Set.

Conclusion

I hope this explanation of my solution was helpful in your search. This is not the only approach and I am interested to hear other peoples strategy in solving the problem. Feel free to leave a comment and let me know! Thanks for taking the time to read!