Sliding Window

def length_of_longest_substring(s: str) -> int:
    """Length of the longest substring of `s` with no repeated character."""
    in_window: set[str] = set()
    left = 0
    best = 0
    for right, c in enumerate(s):
        # A repeat breaks the window, and growing it can't fix that.
        # Drop characters from the left until the earlier copy of c is gone.
        while c in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(c)
        best = max(best, right - left + 1)
    return best


if __name__ == "__main__":
    print(length_of_longest_substring("abcabcbb"))  # 3
    print(length_of_longest_substring("bbbbb"))  # 1
    print(length_of_longest_substring("pwwkew"))  # 3
    print(length_of_longest_substring(""))  # 0

// Length of the longest substring of `s` with no repeated character.
export function lengthOfLongestSubstring(s: string): number {
  const inWindow = new Set<string>();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    // A repeat breaks the window, and growing it can't fix that.
    // Drop characters from the left until the earlier copy of c is gone.
    while (inWindow.has(c)) {
      inWindow.delete(s[left]);
      left++;
    }
    inWindow.add(c);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("bbbbb")); // 1
console.log(lengthOfLongestSubstring("pwwkew")); // 3
console.log(lengthOfLongestSubstring("")); // 0

package main

import "fmt"

// lengthOfLongestSubstring returns the length of the longest substring of s
// with no repeated character.
func lengthOfLongestSubstring(s string) int {
	inWindow := map[byte]bool{}
	left := 0
	best := 0
	for right := 0; right < len(s); right++ {
		c := s[right]
		// A repeat breaks the window, and growing it can't fix that.
		// Drop characters from the left until the earlier copy of c is gone.
		for inWindow[c] {
			delete(inWindow, s[left])
			left++
		}
		inWindow[c] = true
		best = max(best, right-left+1)
	}
	return best
}

func main() {
	fmt.Println(lengthOfLongestSubstring("abcabcbb")) // 3
	fmt.Println(lengthOfLongestSubstring("bbbbb"))    // 1
	fmt.Println(lengthOfLongestSubstring("pwwkew"))   // 3
	fmt.Println(lengthOfLongestSubstring(""))         // 0
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Length of the longest substring of s with no repeated character.
    public static int LengthOfLongestSubstring(string s)
    {
        var inWindow = new HashSet<char>();
        int left = 0, best = 0;
        for (int right = 0; right < s.Length; right++)
        {
            char c = s[right];
            // A repeat breaks the window, and growing it can't fix that.
            // Drop characters from the left until the earlier copy of c is gone.
            while (inWindow.Contains(c))
            {
                inWindow.Remove(s[left]);
                left++;
            }
            inWindow.Add(c);
            best = Math.Max(best, right - left + 1);
        }
        return best;
    }

    public static void Main()
    {
        Console.WriteLine(LengthOfLongestSubstring("abcabcbb")); // 3
        Console.WriteLine(LengthOfLongestSubstring("bbbbb")); // 1
        Console.WriteLine(LengthOfLongestSubstring("pwwkew")); // 3
        Console.WriteLine(LengthOfLongestSubstring("")); // 0
    }
}

import java.util.HashSet;
import java.util.Set;

public class Solution {
    // Length of the longest substring of s with no repeated character.
    static int lengthOfLongestSubstring(String s) {
        Set<Character> inWindow = new HashSet<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // A repeat breaks the window, and growing it can't fix that.
            // Drop characters from the left until the earlier copy of c is gone.
            while (inWindow.contains(c)) {
                inWindow.remove(s.charAt(left));
                left++;
            }
            inWindow.add(c);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(lengthOfLongestSubstring("bbbbb")); // 1
        System.out.println(lengthOfLongestSubstring("pwwkew")); // 3
        System.out.println(lengthOfLongestSubstring("")); // 0
    }
}

from collections import Counter


def min_window(s: str, t: str) -> str:
    """Shortest substring of `s` that contains every character of `t`, repeats
    included, or "" if there isn't one."""
    # need[c] is how many more copies of c the window has to take in.
    # It goes negative when the window holds spares.
    need = Counter(t)
    missing = len(t)  # Characters of t the window still lacks.
    best_start = 0
    best_length = len(s) + 1  # Longer than any real window.
    left = 0
    for right, c in enumerate(s):
        if need[c] > 0:
            missing -= 1  # This copy was still needed.
        need[c] -= 1
        # The window covers t. Shrink it while it still does, keeping the smallest.
        while missing == 0:
            if right - left + 1 < best_length:
                best_start = left
                best_length = right - left + 1
            dropped = s[left]
            need[dropped] += 1
            if need[dropped] > 0:
                missing += 1  # Dropped a copy the window needed.
            left += 1
    return "" if best_length > len(s) else s[best_start : best_start + best_length]


if __name__ == "__main__":
    print(repr(min_window("ADOBECODEBANC", "ABC")))  # 'BANC'
    print(repr(min_window("a", "aa")))  # ''
    print(repr(min_window("a", "a")))  # 'a'

// Shortest substring of `s` that contains every character of `t`, repeats
// included, or "" if there isn't one.
export function minWindow(s: string, t: string): string {
  // need.get(c) is how many more copies of c the window has to take in.
  // It goes negative when the window holds spares.
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  let missing = t.length; // Characters of t the window still lacks.
  let bestStart = 0;
  let bestLength = s.length + 1; // Longer than any real window.
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    const count = need.get(c) ?? 0;
    if (count > 0) missing--; // This copy was still needed.
    need.set(c, count - 1);
    // The window covers t. Shrink it while it still does, keeping the smallest.
    while (missing === 0) {
      if (right - left + 1 < bestLength) {
        bestStart = left;
        bestLength = right - left + 1;
      }
      const dropped = s[left];
      const dropCount = (need.get(dropped) ?? 0) + 1;
      need.set(dropped, dropCount);
      if (dropCount > 0) missing++; // Dropped a copy the window needed.
      left++;
    }
  }
  return bestLength > s.length ? "" : s.slice(bestStart, bestStart + bestLength);
}

console.log(JSON.stringify(minWindow("ADOBECODEBANC", "ABC"))); // "BANC"
console.log(JSON.stringify(minWindow("a", "aa"))); // ""
console.log(JSON.stringify(minWindow("a", "a"))); // "a"

package main

import "fmt"

// minWindow returns the shortest substring of s that contains every character
// of t, repeats included, or "" if there isn't one.
func minWindow(s, t string) string {
	// need[c] is how many more copies of c the window has to take in.
	// It goes negative when the window holds spares.
	need := map[byte]int{}
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	missing := len(t) // Characters of t the window still lacks.
	bestStart := 0
	bestLength := len(s) + 1 // Longer than any real window.
	left := 0
	for right := 0; right < len(s); right++ {
		c := s[right]
		if need[c] > 0 {
			missing-- // This copy was still needed.
		}
		need[c]--
		// The window covers t. Shrink it while it still does, keeping the smallest.
		for missing == 0 {
			if right-left+1 < bestLength {
				bestStart = left
				bestLength = right - left + 1
			}
			dropped := s[left]
			need[dropped]++
			if need[dropped] > 0 {
				missing++ // Dropped a copy the window needed.
			}
			left++
		}
	}
	if bestLength > len(s) {
		return ""
	}
	return s[bestStart : bestStart+bestLength]
}

func main() {
	fmt.Printf("%q\n", minWindow("ADOBECODEBANC", "ABC")) // "BANC"
	fmt.Printf("%q\n", minWindow("a", "aa"))              // ""
	fmt.Printf("%q\n", minWindow("a", "a"))               // "a"
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Shortest substring of s that contains every character of t, repeats
    // included, or "" if there isn't one.
    public static string MinWindow(string s, string t)
    {
        // need[c] is how many more copies of c the window has to take in.
        // It goes negative when the window holds spares.
        var need = new Dictionary<char, int>();
        foreach (char c in t) need[c] = need.GetValueOrDefault(c) + 1;
        int missing = t.Length; // Characters of t the window still lacks.
        int bestStart = 0;
        int bestLength = s.Length + 1; // Longer than any real window.
        int left = 0;
        for (int right = 0; right < s.Length; right++)
        {
            char c = s[right];
            if (need.GetValueOrDefault(c) > 0) missing--; // This copy was still needed.
            need[c] = need.GetValueOrDefault(c) - 1;
            // The window covers t. Shrink it while it still does, keeping the smallest.
            while (missing == 0)
            {
                if (right - left + 1 < bestLength)
                {
                    bestStart = left;
                    bestLength = right - left + 1;
                }
                char dropped = s[left];
                need[dropped]++;
                if (need[dropped] > 0) missing++; // Dropped a copy the window needed.
                left++;
            }
        }
        return bestLength > s.Length ? "" : s.Substring(bestStart, bestLength);
    }

    public static void Main()
    {
        Console.WriteLine(Quote(MinWindow("ADOBECODEBANC", "ABC"))); // "BANC"
        Console.WriteLine(Quote(MinWindow("a", "aa"))); // ""
        Console.WriteLine(Quote(MinWindow("a", "a"))); // "a"
    }

    static string Quote(string text) => "\"" + text + "\"";
}

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

public class Solution {
    // Shortest substring of s that contains every character of t, repeats
    // included, or "" if there isn't one.
    static String minWindow(String s, String t) {
        // need.get(c) is how many more copies of c the window has to take in.
        // It goes negative when the window holds spares.
        Map<Character, Integer> need = new HashMap<>();
        for (int i = 0; i < t.length(); i++) need.merge(t.charAt(i), 1, Integer::sum);
        int missing = t.length(); // Characters of t the window still lacks.
        int bestStart = 0;
        int bestLength = s.length() + 1; // Longer than any real window.
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (need.getOrDefault(c, 0) > 0) missing--; // This copy was still needed.
            need.merge(c, -1, Integer::sum);
            // The window covers t. Shrink it while it still does, keeping the smallest.
            while (missing == 0) {
                if (right - left + 1 < bestLength) {
                    bestStart = left;
                    bestLength = right - left + 1;
                }
                char dropped = s.charAt(left);
                need.merge(dropped, 1, Integer::sum);
                if (need.get(dropped) > 0) missing++; // Dropped a copy the window needed.
                left++;
            }
        }
        return bestLength > s.length() ? "" : s.substring(bestStart, bestStart + bestLength);
    }

    public static void main(String[] args) {
        System.out.println(quote(minWindow("ADOBECODEBANC", "ABC"))); // "BANC"
        System.out.println(quote(minWindow("a", "aa"))); // ""
        System.out.println(quote(minWindow("a", "a"))); // "a"
    }

    static String quote(String text) {
        return "\"" + text + "\"";
    }
}