Window String DSA Problem Solution

Window String DSA Problem Solution

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 (

1S1e4). Second line contains a string t (

1t1e4)

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;

}