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