PROBLEM LINK:
Author: Chandan Boruah
Tester: Tester’s name
Editorialist: Naman Chaurasia
DIFFICULTY: EASY-MEDIUM
PREREQUISITES:
DP, Math
PROBLEM:
Given 2 strings A and B, string A can be converted to string B, by deleting some characters from string A. Create another string C such that it contains the characters deleted from A, while converting string A to B, in increasing order of position in string A.
find the lexicographically smallest string C if possible.
QUICK EXPLANATION:
if i , j be indexes pointing strings A & B
if( A[i] == B[j] ) dp(i,j) = min( dp(i+1,j+1), dp(i+1,j),dp(i,j) )
else
dp(i,j) = min( dp(i+1,j+1),dp(i,j) )
EXPLANATION:
given 2 strings A & B
let i , j be indexes pointing strings A & B respectively.
comparing indexes i, j
A [i] && B [j]
here comes 2 cases
case 1: A[i] != B[j]
this character must be deleted i.e. A[i] will be contained in the string C
in this case compare for(i+1,j) recursively
if i and j comes to end of strings then obtained string can be a probable answer(check for lexographically smallest string among these strings)
case 2: A[i] == B[j]
this character may not be deleted i.e. A[i] will not be contained in the string C
in this case compare for(i+1,j+1) recursively
if i and j comes to end of strings then obtained string can be a probable answer(check for lexographically smallest string among these strings)
also check for(i+1,j) as this character A[i] may be contained in the string C
SOLUTIONS:
Setter's Solution
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
string[]ss=Console.ReadLine().Split();
string a=ss[0];
string b=ss[1];
List<string>ll=new List<string>();
List<string>tt=new List<string>();
for(int j=0;j<1<<a.Length;j++)
{
string yes="";
string done="";
for(int k=0;k<a.Length;k++)
{
if((j&1<<k)!=0)
{
done+=a[k];
}
else yes+=a[k];
}
ll.Add(done);
tt.Add(yes);
}
List<string>all=new List<string>();
for(int i=0;i<ll.Count;i++)
{
if(ll[i]==b)
{
all.Add(tt[i]);
}
}
if(all.Count==0)Console.WriteLine(-1);
else
{all.Sort();Console.WriteLine(all[0]);}
}
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
string s1,s2,ans="zzzzzzzzzz";
int n1,n2;
void fun(int i,int j,string s)
{
if(i==n1)
{
if(j==n2 && ans>s)ans=s;
return ;
}
if(s1[i]==s2[j])fun(i+1,j+1,s);
s.push_back(s1[i]);
fun(i+1,j,s);
s.pop_back();
return ;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
ll t,n,i;
cin>>s1>>s2;
n1=s1.size();n2=s2.size();
fun(0,0,"");
if(ans=="zzzzzzzzzz")ans="-1";
cout<<ans<<"\n";
return 0;
}