Minimum Window Substring

Animated walkthrough

Step through the algorithm visually — use Play or the step buttons (inspired by AlgoMaster / visualgo).

Step 1 / 1

Barclays interview context: Minimum Window Substring is a Hard Sliding Window problem — Maintain a window [L, R] and update counts as you expand or contract.

Use the animation above to step through each move before writing code.

Pattern: Sliding Window

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

Problem

Minimum Window Substring — Barclays interview prep · 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
Frequently asked at Barclays
Sliding Window

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.

Animated walkthrough

Problem

Examples

Your solution

Solution

Discussion