Longest substring without repeats

A variable-size sliding window: grow on the right, and jump the left edge past any repeated character.

Time O(n)Space O(k)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Remember the last index of every character. When the new character was already seen inside the current window, move the left edge to just after that earlier copy.

Code

C++PythonC#

int longestUnique(const string& s) {
    unordered_map<char, int> last; // char -> last index seen
    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;
}

def longest_unique(s: str) -> int:
    last = {}  # char -> last index seen
    best = left = 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = r
        best = max(best, r - left + 1)
    return best

public static int LongestUnique(string s) {
    var last = new Dictionary<char, int>(); // char -> last index seen
    int best = 0, left = 0;
    for (int r = 0; r < s.Length; r++) {
        if (last.TryGetValue(s[r], out int p) && p >= left)
            left = p + 1;
        last[s[r]] = r;
        best = Math.Max(best, r - left + 1);
    }
    return best;
}

Tips

The "p >= left" check matters: an old copy that is already outside the window must not pull left backwards.
k is the alphabet size, so space is effectively constant for ASCII.

In the .NET library

Dictionary<char,int>.TryGetValue does the lookup and the read in one hash probe. Avoid ContainsKey followed by the indexer.