 # Can anybody tell me how to approach this type of question asked in coding contest

2 Likes

may be you can try maintaining three vectors for c,a,t respectively, for storing indexes of their occurrences (occurring in order only) and then applying some logic

ps: share the link of the problem

1 Like
1 Like

thanku very much harjot

1 Like

Can anybody explain the given Setter’s code or atleast add suitable comments in this code:

``````#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int dp[N];

int main(){
int n;
cin >> n;
string s;
cin >> s;
memset(dp, 0, sizeof(dp));
if (s == 'c')
{
dp = 1;
}
for (int i = 1; i < n; i++)
{
if (s[i] == 'c')
{
dp[i] = dp[i - 1] + 1;
}
else
{
dp[i] = dp[i - 1];
}
if (s[i] == 'a')
{
dp[i] = min(dp[i - 1], dp[i - 1] + 1);
}
else
{
dp[i] = dp[i - 1];
}
if (s[i] == 't')
{
dp[i] = min(dp[i - 1], dp[i - 1] + 1);
}
else
{
dp[i] = dp[i - 1];
}
}
int p = 2;
string ans;
for (int i = n - 1; i >= 0; i--)
{
if (i == 0)
{
if (p || !dp)
{
ans += s[i];
}
}
else
{
if (p == 2 && s[i] == 't')
{
if (dp[i - 1] <= dp[i - 1] + 1)
{
ans += s[i];
p--;
}
}
else if (p == 1 && s[i] == 'a')
{
if (dp[i - 1] <= dp[i - 1] + 1)
{
ans += s[i];
p--;
}
}
else if (p == 0 && s[i] == 'c')
{
continue;
}
else
ans += s[i];
}
}
reverse(ans.begin(), ans.end());

cout << ans.size() << "\n";
cout << ans;

return 0;
}``````