Coding

Minimum Window Substring

Asked at

Goldman Sachs

Intuit

MetaWWheelsEye

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given two strings s and t. Find the smallest window substring of s that includes all characters in t (including duplicates) , in the window. Return the empty string "" if no such substring exists.

Input : s = "ADOBECODEBANC" , t = "ABC" Output : "BANC" Explanation : The minimum window substring of string s that contains the string t is "BANC".

Input : s = "a" , t = "a" Output : "a" Explanation : The complete string is the minimum window

Input : s = "aAbBDdcC" , t = "Bc"

1 <= n , m <= 105
n = s.length
m = t.length
string s and t consist of uppercase and lowercase letters.

cpp

class Solution {
public:
    string minWindow(string s, string t) {
         //your code goes here
    }
};

java

class Solution {
    public String minWindow(String s, String t) {
        //your code goes here
    }
}

python

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        #your code goes here

javascript

class Solution {
    minWindow(s, t) {
        //your code goes here
    }
}

csharp

public class Solution {
    public string MinWindow(string s, string t) {

    }
}

func minWindow(s string, t string) string {

}

Stuck? Show a way to structure it+

01Count the required frequency of every character in t.
02Expand the right boundary and update how many required characters are still missing.
03Whenever the window is valid, repeatedly shrink from the left while recording the best window.
04Return the best recorded slice, or an empty string if no valid window was found.

Reference answer

Build a frequency map need from t, including duplicates, and set missing = t.length. Move a right pointer across s. When the incoming character is still needed, decrement missing; then decrement that character's remaining requirement in the map. Counts may become negative, which simply means the window has extra copies.

When missing becomes zero, the current window contains every required character. Now move the left pointer forward while the window remains valid. Before each removal, record the window if it is the smallest seen. Increment the requirement for the outgoing character; if it becomes positive, that removal made the window invalid, so increment missing and resume expanding the right side.

This handles duplicate requirements correctly. For example, t = AABC requires two A characters, not merely the set {A, B, C}. Each pointer moves only forward, so time is O(|s| + |t|). Space is O(alphabet size) or O(number of distinct characters in t). Return an empty string when no best window was recorded.

Then expect these follow-ups

How would you adapt the solution for arbitrary Unicode characters?
Tests: representation choices
What invariant tells you that the current window is valid?
Tests: correctness reasoning

Hiring now

Linkedin has 196 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Staff Software Engineer
Mountain View, CA, United States
Staff Software Engineer, Systems Infrastructure
Bengaluru, KA, India

Or practice this question first

Next question