PROBLEM LINK:
Author & Editorialist: Prakhar Kochar
Tester: Tejas Dhanait, Krish Rustagi
DIFFICULTY:
SIMPLE
PREREQUISITES:
Brute Force , Implementation
PROBLEM:
-
A string consists of lower case english alphabets . You need to convert the given string into Third-Delicious .
-
How to make a Third-Delicious String ?
-
Choose any 3 lower case english alphabets (not necessarily distinct)
Eg. a,b,c -
Arrange 3 alphabets in a particular order to form string A = “abc”
-
A string S of length N is called Third-Delicious if S[i] = A[i % 3] , 0<=i<=N-1 ;
eg. S = “a” , ”ab” , ”abc” , ”abca” , ”abcab” , abcabc”
-
-
You need to find a minimum number of characters that can be deleted from the given string to make it Third-Delicious . Print minimum number of characters deleted from the given string and final Third-Delicious String .
-
If multiple final strings exist , print the lexicographically smallest one .
EXPLANATION:
-
Traverse through all possible combinations of the string of length 3 consisting of lower case english alphabets , in ascending order eg. A = “aaa” , “aab” , “aac” …. “aaz” , “aba” , “abb” ……so on
-
While traversing you just need to find the length of the longest subsequence of the given string that is Third-Delicious by the above combinations . To do so initialize the counters say , len = 0 , fin = “” , now traverse through the given string , check if S[i] = A[len % 3] , then update the counters as len ++ , fin+=S[i].
-
fin contains the Third-Delicious string formed by the combinations .Now you just need to check for fin , with maximum length .
-
If you encounter subsequences of the same length by two different combinations then give preference to the combination that came first , so that lexicographical order is followed .
TIME COMPLEXITY:
O(26*26*26*N)
SOLUTIONS:
Setter's Solution (Python)
import string
s = input(); ans = 10**9; sans = ""
abc = list(string.ascii_lowercase)
for i in range(0,26):
for j in range(0,26):
for k in range(0,26):
l = 0; fin = "";
x = [abc[i],abc[j],abc[k]]
for z in range(0,len(s)):
if s[z] == x[l%3]:
l+=1; fin+=s[z]
if(len(s)-l < ans):
ans = len(s)-l
sans = fin
print(ans,sans,sep=" ")
Tester's Solution (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define ppb pop_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define lp1(i,a,b) for(ll i=a;i<b;i++)
#define lp2(i,a,b) for(ll i=a;i>=b;i--)
#define mod 1000000007
#define endl "\n"
#define bs binary_search
#define mp make_pair
int main()
{
fast
string s;
cin>>s;
string a="";
lp1(i,0,26)
{
lp1(j,0,26)
{
lp1(k,0,26)
{
string ans="";
int f=1;
lp1(l,0,s.size())
{
ll a1=i+97;
ll a2=j+97;
ll a3=k+97;
if(f==1)
{
if(s[l]==char(a1))
{
ans=ans+s[l];
f=2;
}
}
else if(f==2)
{
if(s[l]==char(a2))
{
ans=ans+s[l];
f =3;
}
}
else
{
if(s[l]==char(a3))
{
ans=ans+s[l];
f=1;
}
}
}
if(a.size()<ans.size())
{
a=ans;
}
}
}
}
cout<<s.size()-a.size()<<" "<<a<<endl ;
}