Longest Substring Without Repeating Characters

MediumSliding Window

Return the length of the longest substring that contains no repeating characters.

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces

Sliding window with last-seen index

Time O(n)Space O(min(n, alphabet))

Expand a window to the right and remember each character's most recent index. When a repeat falls inside the window, jump the left edge just past the previous occurrence. The answer is the largest window width seen.

#include <bits/stdc++.h>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> last;
    int best = 0, left = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        auto it = last.find(s[r]);
        if (it != last.end() && it->second >= left) left = it->second + 1;
        last[s[r]] = r;
        best = max(best, r - left + 1);
    }
    return best;
}