Why cast the char to unsigned char before indexing?

Whether plain char is signed depends on the platform, and on x86 GCC it is. A byte above 127 then becomes a negative number, and last[s[i]] reads outside the vector. (unsigned char) maps every byte to 0..255, which is why the table has 256 slots.

unordered_map or a 256-entry table?

Both give O(n). The table needs no hashing or allocation per character and is noticeably faster; the map only stores what it meets. With an unordered_map use find for the lookup, because last[c] inserts a default 0 for a missing key and would look like a character seen at index 0.

Does this work with UTF-8 text?

std::string holds bytes, and a character such as é is two bytes in UTF-8, so the code finds the longest run of distinct bytes, not characters. For real Unicode, decode to std::u32string or a vector of code points first and key an unordered_map by them.

Should the parameter be const string& instead of string?

Taking const string& avoids a copy and is what you would write in your own code. The signature here takes string by value; the copy is one O(n) pass, which does not change the complexity.

Why check last[c] >= left before moving the left edge?

The table remembers characters that have already slid out of the window. Without the check left can jump backwards to a stale index, and "noon" returns 3 instead of 2. left = max(left, last[c] + 1) is the same rule in one line.

Longest Substring Without Repeating Characters in C++: Sliding Window Solutions

length_of_longest_substring.cpp

C++ 15.3

Not run yet

+ 8 hidden

Input

s = "streetcar"

Expected

The double e breaks the word up. After it, "etcar" has five different characters.