DEV Community

Cover image for LeetCode Challenge: 76. Minimum Window Substring - JavaScript Solution ๐Ÿš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 1 1 1 1

LeetCode Challenge: 76. Minimum Window Substring - JavaScript Solution ๐Ÿš€

Top Interview 150

The Minimum Window Substring problem requires finding the smallest substring of s that contains all characters from t. Letโ€™s solve it step by step using an efficient sliding window approach.


๐Ÿš€ Problem Description

Given strings s and t, return the smallest substring of s such that all characters in t (including duplicates) are included in the substring. If no such substring exists, return an empty string "".


๐Ÿ’ก Examples

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"  
Output: "BANC"  
Explanation: The substring "BANC" contains all characters 'A', 'B', and 'C'.
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: s = "a", t = "a"  
Output: "a"  
Explanation: The entire string `s` matches `t`.
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: s = "a", t = "aa"  
Output: ""  
Explanation: `t` requires two 'a's, but `s` only has one.
Enter fullscreen mode Exit fullscreen mode

๐Ÿ† JavaScript Solution

We will solve this using a sliding window and hash maps to keep track of character frequencies.


Implementation

var minWindow = function(s, t) {
    if (s.length < t.length) return "";

    const tFrequency = {};
    for (let char of t) {
        tFrequency[char] = (tFrequency[char] || 0) + 1;
    }

    let left = 0;
    let right = 0;
    let formed = 0;
    const windowFrequency = {};
    let minLength = Infinity;
    let minWindow = "";

    const required = Object.keys(tFrequency).length;

    while (right < s.length) {
        const char = s[right];
        windowFrequency[char] = (windowFrequency[char] || 0) + 1;

        if (tFrequency[char] && windowFrequency[char] === tFrequency[char]) {
            formed++;
        }

        while (formed === required) {
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                minWindow = s.substring(left, right + 1);
            }

            const leftChar = s[left];
            windowFrequency[leftChar]--;
            if (tFrequency[leftChar] && windowFrequency[leftChar] < tFrequency[leftChar]) {
                formed--;
            }
            left++;
        }

        right++;
    }

    return minWindow;
};
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” How It Works

  1. Frequency Map for t:

    • Create a hash map tFrequency to store the count of each character in t.
  2. Sliding Window:

    • Use two pointers (left and right) to define a dynamic window in s.
    • Expand the window by moving right.
    • Contract the window by moving left when all characters in t are present.
  3. Update Minimum Window:

    • When the window contains all characters in t (i.e., formed === required), check if itโ€™s the smallest window so far.

4.Return Result:

  • Return the smallest substring stored in minWindow.

๐Ÿ”‘ Complexity Analysis

  • Time Complexity: O(m+n), where m is the length of s and n is the length of t.

    • Each character in s is processed at most twice (once by right and once by left).
  • Space Complexity: O(n+m), where n is the size of tFrequency and m is the size of windowFrequency.


๐Ÿ“‹ Dry Run

Input: s = "ADOBECODEBANC", t = "ABC"

Dry Run
Output: "BANC"


โœจ Pro Tips for Interviews

  1. Explain Sliding Window:

    • Highlight its efficiency in reducing unnecessary computations by dynamically adjusting the window size.
  2. Discuss Edge Cases:

    • s shorter than t.
    • Characters in t not in s.
    • Multiple valid substrings with the same minimum length.
  3. Highlight Efficiency:

    • Compare this O(m+n) solution with naive O(mโ‹…n) approaches that check all substrings.

๐Ÿ“š Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
๐Ÿ‘‰ Substring with Concatenation of All Words - JavaScript Solution

Whatโ€™s your approach to solving this problem? Letโ€™s discuss! ๐Ÿš€


Study

Image of Docusign

๐Ÿ› ๏ธ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (1)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal โ€ข

Follow Me on GitHub ๐Ÿš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Sentry image

See why 4M developers consider Sentry, โ€œnot bad.โ€

Fixing code doesnโ€™t have to be the worst part of your day. Learn how Sentry can help.

Learn more

๐Ÿ‘‹ Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay