KQM23A editorial

PROBLEM LINK:

Contest
Practice

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;

}