In this post, we are going to solve Window String DSA Problem from Amazon’s 10th October Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.
Window String DSA Problem Statement
Given two strings ‘s’ and ‘t’ containing characters from a to z of lengths ‘m’ and ‘n’ respectively, return the minimum window substring of ‘s’ such that every character in ‘t’ (including duplicates) is included in the window. If there is no such substring, return the empty string “”‘.
Input
The first line of input contains string s (
). Second line contains a string t (
)
Output
For each output print the substring of the minimum window.
Example
Input
adovecodebanc abc
Output
banc
Window String DSA Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
string s,t;
cin>>s>>t;
int ct=0;
vector<int> ft(26,0);
for(auto x:t)
{
if(ft[x-'a']==0)
ct++;
ft[x-'a']++;
}
vector<int> f(26,0);
int n=s.length();
int cc=0;
int beg=0;
int ans=n;
int l=-1,r=n+1;
for(int i=0;i<n;i++)
{
f[s[i]-'a']++;
if(f[s[i]-'a']==ft[s[i]-'a'])
{
cc++;
}
while(cc==ct)
{
if(f[s[beg]-'a']==ft[s[beg]-'a'])
{
if(i-beg<ans)
{
ans=i-beg;
l=beg,r=i;
}
cc--;
}
f[s[beg]-'a']--;
beg++;
}
}
if(l!=-1)
{
cout<<s.substr(l,r-l+1);
}
else
cout<<"";
return 0;
}