Minimum Window Substring

Problem

Minimum Window Substring — DSA Interview 150 · Sliding Window

Classic interview problem #76.

Input (stdin)

Line 1: s\nLine 2: t

Output (stdout)

Minimum window substring (or empty)

Your program must read from stdin and write the answer to stdout (no extra debug text).

Examples

Sample

Input

ADOBECODEBANC
ABC

Output

BANC

Hints

Input format: Line 1: s\nLine 2: t
DSA Interview 150 — Sliding Window
Problem #76

Your solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

static void Main()
    {
        // Read from stdin (see problem statement for format)
        // Line 1: s\nLine 2: t

}
}

Ready — edit the code above and click Run or Submit.

Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

    static void Main()
    {
string s = Console.ReadLine();
string t = Console.ReadLine();
var need = new Dictionary<char, int>();
foreach (var c in t) need[c] = need.GetValueOrDefault(c) + 1;
int have = 0, goal = need.Count, start = 0, bestLen = int.MaxValue, bestStart = 0;
var window = new Dictionary<char, int>();
for (int end = 0; end < s.Length; end++) {
    char c = s[end];
    window[c] = window.GetValueOrDefault(c) + 1;
    if (need.ContainsKey(c) && window[c] == need[c]) have++;
    while (have == goal) {
        if (end - start + 1 < bestLen) { bestLen = end - start + 1; bestStart = start; }
        char left = s[start++];
        window[left]--;
        if (need.ContainsKey(left) && window[left] < need[left]) have--;
    }
}
Ws(bestLen == int.MaxValue ? "" : s.Substring(bestStart, bestLen));
    }
}

Try solving on your own first, then reveal the official answer.

Explanation

Pattern: Sliding Window

Read from stdin, write to stdout. Classic interview problem #76.

Problem

Examples

Your solution

Solution

Explanation

Discussion