Longest Substring With All Unique Characters

medium string sliding window

Problem

Given a string, return the length of the longest contiguous substring whose characters are all distinct.

Use a sliding window [l, r]. Walk r forward; if the character at r is already inside the window, jump l to one past the previous position of that character. The window is always duplicate-free.

Inputs = "abcadcbe"

Output5

"adcbe" (positions 3..7) has all distinct characters and length 5.

def longest_unique(s):
    last = {}
    l = best = 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= l:
            l = last[ch] + 1
        last[ch] = r
        if r - l + 1 > best:
            best = r - l + 1
    return best

function longestUnique(s) {
  const last = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    const ch = s[r];
    if (last.has(ch) && last.get(ch) >= l) {
      l = last.get(ch) + 1;
    }
    last.set(ch, r);
    if (r - l + 1 > best) best = r - l + 1;
  }
  return best;
}

class Solution {
    public int longestUnique(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            char ch = s.charAt(r);
            if (last.containsKey(ch) && last.get(ch) >= l) {
                l = last.get(ch) + 1;
            }
            last.put(ch, r);
            if (r - l + 1 > best) best = r - l + 1;
        }
        return best;
    }
}

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

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