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.
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
Contact Us