Smallest Window in a String Containing all the Characters of Another String using JavaScript
Given two strings, “str” (the larger string) and “pattern” (the smaller string), the task is to find the smallest window in “str” that contains all the characters of “pattern” in any order using JavaScript.
Examples:
Input:
str = "ADOBECODEBANC"
pattern = "ABC"
Output: BANC
Input:
str = "this is a test string"
pattern = "tist";
Output: t stri
Table of Content
- Sliding Window Technique
- Frequency Map
Sliding Window Technique
In this approach, we are iteratively sliding a window over the larger string (“str”), ensuring it contains all characters of the smaller string (“pattern”). It initializes two pointers, left and right, and expands the window to the right until all characters of “pattern” are included. Once a valid window is found, it updates the minimum window length and shifts the left pointer to contract the window until it no longer contains all characters of “pattern”. This process continues until the end of “str” is reached, and the minimum window found is returned.
Example: Implementation of program Smallest window in a string containing all the characters of another string using Sliding Window Technique
function minWindow(str, pattern) {
let patternMap = new Map();
for (let char of pattern) {
patternMap.set(char,
patternMap.get(char) + 1 || 1);
}
let left = 0,
right = 0,
minLen = Infinity,
minStart = 0,
count = pattern.length;
while (right < str.length) {
if (patternMap.has(str[right])
&& patternMap.get(str[right]) > 0) {
count--;
}
patternMap.set(str[right],
(patternMap.get(str[right]) || 0) - 1);
right++;
while (count === 0) {
if (right - left < minLen) {
minLen = right - left;
minStart = left;
}
patternMap.set(str[left],
patternMap.get(str[left]) + 1);
if (patternMap.get(str[left]) > 0) {
count++;
}
left++;
}
}
return minLen === Infinity ? ""
: str.substr(minStart, minLen);
}
// Example usage:
let str = "ADOBECODEBANC";
let pattern = "ABC";
console.log(minWindow(str, pattern));
Output
BANC
Time Complexity: O(N), where n is the length of the string “str”, as each character is visited at most twice.
Auxiliary Space: O(m),where m is the length of the pattern, for the patternMap.
Frequency Map
In this approach, we create a frequency map for the characters in “pattern” to track their occurrences. Then we iterate through “str” while maintaining a window containing all characters of “pattern”. As it expands the window to the right, it updates the frequency map accordingly. When a valid window is found, it calculates the window length and shifts the left pointer to minimize the window size while still containing all characters of “pattern”. This process continues until the end of “str” is reached, and the minimum window found is returned.
Example: Implementation of program to Smallest window in a string containing all the characters of another string using Frequency Map.
function minWindow(str, pattern) {
let patternMap = new Map();
for (let char of pattern) {
patternMap.set(char,
patternMap.get(char) + 1 || 1);
}
let left = 0,
right = 0,
minLen = Infinity,
minStart = 0,
count = pattern.length;
while (right < str.length) {
if (patternMap.has(str[right])) {
if (patternMap.get(str[right]) > 0) {
count--;
}
patternMap.set(str[right],
patternMap.get(str[right]) - 1);
}
right++;
while (count === 0) {
if (right - left < minLen) {
minLen = right - left;
minStart = left;
}
if (patternMap.has(str[left])) {
patternMap.set(str[left],
patternMap.get(str[left]) + 1);
if (patternMap.get(str[left]) > 0) {
count++;
}
}
left++;
}
}
return minLen === Infinity ? ""
: str.substr(minStart, minLen);
}
let str = "ADOBECODEBANC";
let pattern = "ABC";
console.log(minWindow(str, pattern));
Output
BANC
Time Complexity: O(N), where n is the length of the string “str”, as each character is visited at most twice.
Auxiliary Space: O(m), where m is the length of the pattern, for the patternMap.