hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Smallest Window


  • Approach:

    1. A very interesting Two Pointer problem.

    2. Count the frequency of every character of string X say, freq.

    3. n = size of S, m = size of X.

    4. Declare the variables, left = 0, right = 0, start = 0, end = n-1, ansSize = n.

    5. left => left pointer of string S, right => right pointer of string S, start = start pointer of the minimized window, end = end pointer of the minimized window, ansSize = size of the minimized window, letters = total characters encountered from S, that are also in X,

    6. Initiate another character frequency counter for S say, newFreq.

    7. For the string, S, increase the right pointer one by one and process the current right'th character.

    8. Increase the newFreq by 1.

    9. If the newFreq for the current character is less than the freq for the current character, the increase letters by 1.

    10. Run a loop inside when the count of letters remains equal to m.

      • If (right-left+1) < ansSize, then reset start = left; ends = right; ansSize = right - left + 1.

      • Start increasing the left pointer by 1 and process for the left'th character.

      • Reduce the newFreq[s[left]] by 1.

      • If newFreq[s[left]] is lesser than freq[s[left]], then reduce letters by 1.

    11. Keep doing steps 7 - 10, until the right pointer crosses n.

    12. Return the substring from start to end.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1)


Code [C++]

#include <bits/stdc++.h>

string smallestWindow(string s, string x)

{

int n = s.size(), m = x.size();

int freq[128] = {0}, newFreq[128] = {0};

for(int i=0; i<x.size(); i++){

freq[x[i]]++;

}

int start = 0, ends = n - 1;

int left = 0, right = 0, ansSize = n;

int letters = 0;

while(right < n){

newFreq[s[right]]++;

if(newFreq[s[right]] <= freq[s[right]]) letters++;

while(letters == m){

if(right - left + 1 < ansSize){

start = left; ends = right; ansSize = right - left + 1;

}

newFreq[s[left]]--;

if(newFreq[s[left]] < freq[s[left]]){

letters--;

}

left++;

}

right++;

}

// cout<<start<<' '<<ends<<endl;

string ansStr = "";

for(int i=start; i<=ends; i++){

ansStr += s[i];

}

return ansStr;

}