Daily bit(e) of C++ | Maximum substring with unique characters.
Daily bit(e) of C++ #121, Common interview problem: maximum substring with unique characters.
Today we will look at a common interview problem: Maximum substring with unique characters.
Given a string, determine the length of the maximum substring that contains only unique characters.
For example, for the string "abcbef" the longest substring is “cbef”, i.e. four characters long.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/YTWfnGfcz.
Solution
We can use the sliding window approach since we are looking for consecutive elements.
We will extend the window to the right until we hit a duplicate. Then we will shrink the window from the left until we remove the duplicate. Repeat until we have scanned through the entire string.
However, we can do better if we remember the last instance of each letter. Instead of shrinking the string, we can jump directly to the duplicate character. With this approach, we must be careful when checking for duplicates. A character is only a duplicate if its last seen index is after the left border.
