LeetCode Problem 3 - Longest Substring Without Repeating Characters
In this post we’ll be talking about solving the third LeetCode problem. You can find my code for all my LeetCode submissions at GitHub.
LeetCode is a site that provides programming problems for practice. A lot of developers use it to hone their skills or to practice for upcoming interviews. The questions available are used by large tech companies as interview questions, so it’s a good place to start and the difficulty of the questions being Easy, Medium or Hard.
While the solutions for these problems are available directly from the site, they are directly to the point and can be a bit technical. I’d like to use these types of posts to explain the thought process to get to the solution, and how to think about and test for edge cases. I’ll be using C# in dotnet to create my solution. Download Visual Studio for free to create your own.
The Problem
Given a string s, find the length of the longest substring without repeating characters.
The link to the problem can be found here.
Luckily, the problem is pretty straight forward on this one and not a lot of explaination needs to go into it. Simply put, we want to find a string within our input string that has the most unique characters. It could be the whole string itself even, who knows!
Lets look at some test cases to see some examples.
The Test Cases
I am a huge believer in automated testing. Unit testing, integration testing, end to end testing, they are all needed to make sure you have confidence in the quality of your code. Your product is only as good as your tests. That said, of course we’re going to unit test our solution before submission!
Since this problem is pretty straight forward, I didn’t need any auxilary code to help facilitate testing. That kind of stinks, because I like doing it. It’s fun!
There are two test cases that stick out in my mind immediately. First, an empty string. This would and should return the value 0, because there is no substring at all. Next, is when every character in the string is unique so the output is just the length of the string itself.
[Test]
public void ShouldReturnTheWholeThing()
{
var str = "qwertyuiop";
var res = _sut.LengthOfLongestSubstring(str);
res.ShouldBe(str.Length);
}
[Test]
public void ShouldReturnZeroIfEmpty()
{
var res = _sut.LengthOfLongestSubstring("");
res.ShouldBe(0);
}
Another that jumps out after thinking of all the characters being unique is, what if they are all the same character. What if there is only one character total?
[Test]
public void ShouldReturnOneIfOneCharacter()
{
var str = "o";
var res = _sut.LengthOfLongestSubstring(str);
res.ShouldBe(str.Length);
}
[Test]
public void ShouldReturnOneIfAllTheSame()
{
var str = "bbbbb";
var res = _sut.LengthOfLongestSubstring(str);
res.ShouldBe(1);
}
The last three significant tests I can think of are, what if the longest string is in the beginning of the string, the end of the string or smack dab in the middle?
[Test]
public void ShouldReturnLongStringAtBeginning()
{
var str = "poiuytytweqwrtwyr";
var res = _sut.LengthOfLongestSubstring(str);
res.ShouldBe(6);
}
[Test]
public void ShouldReturnLongStringAtTheEnd()
{
var str = "rywtrwqewtytyuiop";
var res = _sut.LengthOfLongestSubstring(str);
res.ShouldBe(6);
}
[Test]
public void ShouldReturnLongStringInTheMiddle()
{
var str = "qweqrrplikfudjggtyr";
var res = _sut.LengthOfLongestSubstring(str);
res.ShouldBe(10);
}
The most frustrating part of making these tests were trying to come up with strings that actually fit the test case I was trying to find. I kept accidentally making them shorter or longer than they had to be and felt like I spent more time debugging the actual tests than the solution itself! But we got through it and thought of quite a few edge cases along the way.
The Solution
This problem is about searching though a string for substrings. Generally in these kinds of scenarios we’re going to loop inside a loop. My thought process here is to loop through each character of the string and inside that loop, begin an inner loop that starts at the next character in the string. We’ll store any character we’ve seen along the way in a Dictionary<char,bool> and if we come across that character again, we know we finished this particular substring.
If the length of the substring we just found was the longest so far, we’ll update our max length found so far, and continue to the next character in the string.
We take a couple shortcuts in the beginning of the code to cover our edge cases of string lengths 0 and 1. Here is my solution function.
public int LengthOfLongestSubstring(string s)
{
if(s.Length == 0)
return 0;
if (s.Length == 1)
return 1;
var maxLength = 1;
var curLength = 0;
var chars= new Dictionary<char, bool>();
for (var i = 0; i < s.Length; i++)
{
chars.Clear();
var firstChar = s[i];
chars[firstChar] = true;
curLength = 1;
for (var j = i+1; j < s.Length; j++)
{
var currentChar = s[j];
if (chars.ContainsKey(currentChar))
{
if (j == s.Length - 1)
{
return maxLength;
}
break;
}
chars[currentChar] = true;
curLength++;
if (maxLength <= curLength)
maxLength = curLength;
if (j == s.Length - 1)
{
return maxLength;
}
}
}
return maxLength;
}
Conclusion
As per usual, there are many ways to solve problems like this. I, personally, try to take understandable and readable approaches. The reason being is that I generally work with other developers. The smaller and more understandable the pieces of the puzzle are for any given problem, the easier it is to put the pieces together and fix any pieces along the way.
You can find all my LeetCode submissions at GitHub. I hope this was helpful and look forward to more problem solutions in the future.
