Longest Substring Without Repeating Characters

Medium Strings

Find the length of the longest substring with all distinct characters, using a sliding window with a last-seen index map.

Sample input

abcabcbb

Sample output

Solution

def length_of_longest(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(length_of_longest("abcabcbb"))

function lengthOfLongest(s) {
  const seen = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (seen.has(ch) && seen.get(ch) >= left) {
      left = seen.get(ch) + 1;
    }
    seen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(lengthOfLongest("abcabcbb"));

import java.util.HashMap;
import java.util.Map;

public class Main {
    static int lengthOfLongest(String s) {
        Map<Character, Integer> seen = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (seen.containsKey(ch) && seen.get(ch) >= left) {
                left = seen.get(ch) + 1;
            }
            seen.put(ch, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongest("abcabcbb"));
    }
}

fun lengthOfLongest(s: String): Int {
    val seen = HashMap<Char, Int>()
    var left = 0
    var best = 0
    for (right in s.indices) {
        val last = seen[s[right]]
        if (last != null && last >= left) {
            left = last + 1
        }
        seen[s[right]] = right
        best = maxOf(best, right - left + 1)
    }
    return best
}

fun main() {
    println(lengthOfLongest("abcabcbb"))
}

func lengthOfLongest(_ s: String) -> Int {
    var seen = [Character: Int]()
    let chars = Array(s)
    var left = 0, best = 0
    for right in 0..<chars.count {
        if let last = seen[chars[right]], last >= left {
            left = last + 1
        }
        seen[chars[right]] = right
        best = max(best, right - left + 1)
    }
    return best
}

print(lengthOfLongest("abcabcbb"))

int lengthOfLongest(String s) {
  final seen = <String, int>{};
  int left = 0, best = 0;
  for (var right = 0; right < s.length; right++) {
    final ch = s[right];
    if (seen.containsKey(ch) && seen[ch]! >= left) {
      left = seen[ch]! + 1;
    }
    seen[ch] = right;
    final len = right - left + 1;
    if (len > best) best = len;
  }
  return best;
}

void main() {
  print(lengthOfLongest('abcabcbb'));
}

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

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

int main() {
    cout << lengthOfLongest("abcabcbb") << endl;
    return 0;
}

#include <stdio.h>

int lengthOfLongest(const char *s) {
    int lastIndex[256];
    for (int i = 0; i < 256; i++) lastIndex[i] = -1;
    int left = 0, best = 0;
    for (int right = 0; s[right]; right++) {
        unsigned char ch = s[right];
        if (lastIndex[ch] >= left) {
            left = lastIndex[ch] + 1;
        }
        lastIndex[ch] = right;
        int len = right - left + 1;
        if (len > best) best = len;
    }
    return best;
}

int main() {
    printf("%d\n", lengthOfLongest("abcabcbb"));
    return 0;
}