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.
int max_unique_substring(std::string_view s) {
int64_t max_len = 0;
// initial left border, before the start of the string
int64_t left = -1;
// storage for last instance of each character
std::vector<int64_t> arr(256,-1);
for (int64_t right = 0; right < std::ssize(s); ++right) {
// last seen is in between left and right
// this is a duplicate, move left to the duplicate
if (arr[unsigned(s[right])] > left)
left = arr[unsigned(s[right])];
// remember the new last seen
arr[unsigned(s[right])] = right;
// left to right, but not including the character at left
max_len = std::max(max_len, right-left);
}
return max_len;
}