Given a string, find the length of the longest substring without repeating characters.
For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
The trivial solution would be to do double for loop and from each position try to find the longest substring until we see a duplicate char. This is O(n^2) solution.
Faster Solution
We can avoid double loop by caching the last seen position of a character and check at each position if current character is present in the the cache. Note that, while we traverse form left to right if we see a character at position j is a duplicate of a character at a position i < j on the left then we know that we can't start the substring from i anymore. So, we need to start a new substring from i+1 position. While doing this we also need to update the length of current substring and start of current substring. Important part of this process is to make sure that we always keep the latest position of the characters we have seen so far. Below is a simple O(n) implementation of this logic.
Read full article from Longest sub-string with no duplicate chars - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment