link to the problem:
approach: firstly i am storing the number of occurences of every character “U”,“D”,“R”,“L” in a map named str. then i am storing the required number of occurences of each “U”,“D”,“R”,“L” in a map req. And if all the occurences in the map str are greater then the required occurences which are stored in map req, then i am returning "YES " with the count else return “NO”.
getting tle but the time complexity of code is around O(10^7)…
Please help me…
link to my solution:
https://www.codechef.com/viewsolution/37012072
#include<bits/stdc++.h>
#define lli long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
using namespace std;
int main()
{
fastio;
lli t;
cin>>t;
while(t- -)
{
string s;
cin>>s;
map<char,lli>str;
for (int i=0;i<s.size();i++)
{
str[s[i]]++;
}
lli x,y;
cin>>x>>y;
lli q;
cin>>q;
while(q- -)
{
lli count=0;
map<char,lli>req;
req['R']=0;
req['L']=0;
req['U']=0;
req['D']=0;
lli x1,y1;
cin>>x1>>y1;
if (x1>x)
{
req['R']=x1-x;
count+=x1-x;
}
if (x1<x)
{
req['L']=x-x1;
count+=x-x1;
}
if (y1>y)
{
req['U']=y1-y;
count+=y1-y;
}
if (y1<y)
{
req['D']=y-y1;
count+=y-y1;
}
if (str['D']>=req['D'] && str['L']>=req['L'] && str['U']>=req['U'] && str['R']>=req['R'] )
{
cout<<"YES"<<" "<<count<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
}
}