Understanding the ‘Longest Substring Without Repeating Characters’
While working in the Computer Science lab at Boston University, I encountered a problem related to Write Ahead Log (WAL) in databases. I cannot disclose the complete problem statement but it boiled down to finding the length of the longest substring that exists without repeating characters. If you didn’t understand why it was needed, you might as well ignore this paragraph. So, let’s jump to the solution instead.
The problem is pretty standard: Given a string, find the length of the longest substring without repeating characters.
So, if you have ‘aviral’, the longest substring is ‘viral’ with the length of five characters. I needed the length for my WAL, so my aim was to just get the length 5.
I will explain the solution in simple words, without getting into the algorithm, data structures, and the final code for it.
The problem requires us to find the substring, that means we can traverse the string and as soon as we encounter an already occurred character from behind, we can stop right there. But then, we will have to decide whether the string formed until now(before the duplicate strikes) is longer or the string that could be formed without the initial occurrence of this duplicated character. So, while traversing ‘aviral’, you would realize that the fifth character: ‘a’ has already occurred. So, we have to make the decision that the string formed until now(‘avir’) would be longer than ‘vira’ and the characters after the second ‘a’. This makes you note down that the last occurrence of each character is important as well so that the further string’s length can be calculated and compared with the current string’s length.
So, to jot down:
- store from where to start the next time if you encounter a repeated character
- calculate the length of the current string and compare it with the current maximum length that you have; whichever is the largest, that is the maximum length.
My code snippet is this:
In case this code is not good enough, you can dive into other websites’ material like Codechef, etc.
Let me know in the comments if you couldn’t understand anything. It’s always exciting for me whenever I get to apply algorithms or competitive coding to my real development work.