Sunday, April 12, 2020

Longest Substring Without Repeating Characters

Hello everyone,

Today we will be going over the "Longest Substring Without Repeating Characters" problem provided by Leetcode.

Longest Substring Without Repeating Characters

In this problem, we need to find the length of the longest substring without repeating characters, given a string.

Solution

I first started with a brute force solution. However, I quickly learned how large strings can get and how slowly this solution was.

I then came up with a new solution. In this new solution will utilize two points called "i" and "j". "i" will start at the first index of the string, while "j" starts at the second index of the string. The idea is that "i" marks the beginning of a substring, while "j" will traverse the string until it hits a character it already seen before. When this happens, "i" is set the the index of "j" and "j" is set to be "i + 1". Although this solution is faster than the brute force solution, I wasn't able to past the tests:
 
The reason I was not able to pass this test, and any other tests past this, was because my second solution was skipping over the substring "vdf" because "i" would be set to an index value of 2 when "j" hits the second "d" in the string.

To fix this issue, I made it so that when "j" hits a repeated character, we set "i" to be "i + 1", so then we do not miss substrings like "vdf" in the string "dvdf."

Results


With the last solution I came up with, I was able to have a fast runtime of 68 ms. Although it is fast, looking at the runtime distribution for this problem I was on the slow end of the curve. There was one solution that apparently had a runtime of 0 ms, which is incredible! When it comes to memory, I was on the low end of the curve, so I think that is pretty good.

Conclusion

It has been a long time since I seen this problem, so the details are pretty scarce. I feel pretty good about the runtime achieved by the passing solution, even if I was on the slow end of the runtime distribution. I found that I still was not finished with the "String to Integer (atoi)" problem, so expect a write up about it soon. Thank you for reading and see you next time!

Link to Source Code: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Longest%20Substring%20Without%20Repeating%20Characters.cpp

Container With Most Water

Hello everyone!

It has been a 8 months since my last post, as I was busy with school. Although school is still going on, I am going to try to keep doing Leetcode problems and these write ups. With that being said, today we will be going over the "Container With Most Water" problem from Leetcode. This problem had some interesting solutions, which we will be going over in this post. As always, source code is at the end of the post. Without further adieu, lets get right into it!

Container With Most Water

The given array gives us information of the position and heights of the given lines. Using this information, we need to find the maximum area of water the container can contain.

One thing to note is that the height used in the area calculation is the smallest height of the two lines (as shown in the example). Also, we are not told about a time requirement; though I did ran into some time issues when trying to submit my code the first time on Leetcode.

Solution

I first tried solving the problem using a brute force solution. What this solution does is that it tests every possible combination of width and height to find the maximum area. This is done by having an outer loop pick one line, and then have an inner loop go through the rest of the lines:

Since we are using two loops, we get a time complexity of O(N^2). When I submitted the brute force solution, I ended up exceeding the given time limit:
One reason would be the O(N^2) time complexity from the usage of two loops. The main issue would be that the loops would do the same calculations repeatedly (same lines and width). After thinking about the example for a bit, I realized that I can optimized by code by ignoring the lines behind the one I am testing:
The idea is that the lines behind "Line 1" was tested with Line 1 beforehand, meaning we do not have to conduct those calculations again. Following this procedure, by the time we get to the very last line in the array, we do not need to do any tests because every line before the last line was tested with the last line (it can be confusing to wrap one's head around).

This keeps the time complexity relatively close to O(N^2), but it is a faster solution.

Result

These are the results from my optimized brute force solution. I knew that the solution was going to be very slow, especially with the last test case being a large array of lines. I was looking at the official solutions to see how to achieve a faster run time, with one cleverly using double pointers and the fact that the height used in the area calculation is limited by the smallest line; giving a O(N) solution rather than my O(N^2).

Conclusion

Overall, this was yet another interesting problem to ponder about. Although my code has a long run time, it shows that sometimes a slow time complexity solution can still work if you optimized the right part of the code. I will be spending some time looking for a new problem and solving it as usual. Thank you for reading and I will see you then!

Longest Substring Without Repeating Characters

Hello everyone, Today we will be going over the "Longest Substring Without Repeating Characters" problem provided by Leetcode. ...