# PROBLEM LINK:

Author: Chandan Boruah
Tester: Tester’s name
Editorialist: Naman Chaurasia

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;

}
``````