DILEMMA - Editorial

editorial
, ,
1

PROBLEM LINK:

Chef in Dilemma
Chef Dynasty

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 ?

    1. Choose any 3 lower case english alphabets (not necessarily distinct)
      Eg. a,b,c

    2. Arrange 3 alphabets in a particular order to form string A = “abc”

    3. 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 ;
}
5 Likes