KQM19B - Editorial

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester 1: Harsh Raj
Tester 2: Mostafijur Riju
Editorialist: Chandan Boruah

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Next Permutation Algorithm, Greedy.

PROBLEM:

Given a string S and a list of words A, find the maximum number of words that can be formed by choosing characters from the string S from left to right.

QUICK EXPLANATION:

Permute through all the possible sequences of words of array A. Then greedily fill up the words in each sequence from S, and find the maximum number of words that can be formed.

EXPLANATION:

It looks like a dynamic programming problem, but is greedy. Since we can choose the characters from left to right, so choosing the characters as they appear in the words will lead to maximum words chosen. Also since words need not be in sequence, so we can permute the sequence of words.

SOLUTIONS:

Setter's Solution
using System;
using System.Collections.Generic;
class some
{
	public static int[]arr;
	public static void Main()
	{
		string s=Console.ReadLine();
		int n=int.Parse(Console.ReadLine());
		arr=new int[n];
		string[]words=Console.ReadLine().Split();
		for(int i=0;i<n;i++)
		{
			arr[i]=i;
		}
		int max=0;
		List<string>vv=new List<string>();
		while(true)
		{
			if(arr[0]==-1)break;
			string now="";
			int[]vals=new int[n];
			int k=0;
			foreach(int ii in arr)
			{
				now+=words[arr[ii]];
				vals[k++]=words[arr[ii]].Length;	
			}
			k=0;		
			for(int i=0;i<s.Length;i++)
			{
				if(k>=now.Length)break;
				if(s[i]==now[k])
				{
					k++;
				}
			}
			int count=0;
			int sum=0;
			for(int i=0;i<vals.Length;i++)
			{
				sum+=vals[i];
				if(sum>k)
				{
					break;
				}count++;
			}
			max=Math.Max(max,count);
			nextPerm();	
		}
		Console.WriteLine(max);
	}
	public static void nextPerm()
	{
		int p=-1;
		for(int i=0;i<arr.Length-1;i++)
		{
			if(arr[i+1]>arr[i])
			{
				p=i;
			}
		}
		if(p==-1){arr[0]=-1;return;}
		int q=-1;
		for(int i=arr.Length-1;i>p;i--)
		{
			if(arr[i]>arr[p])
			{
				q=i;break;
			}	
		}
		if(q==-1){arr[0]=-1;return;}
		int temp=arr[p];
		arr[p]=arr[q];
		arr[q]=temp;
		for(int i=q,j=arr.Length-1;i<j;i++,j--)
		{
			temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
		}
		return;
	}
}
harshraj22's Solution
from collections import defaultdict

text = input()
n = int(input().strip())
words = list(input().strip().split())

ans = 0
for word in words:
	if word in text:
	    ans += 1

print(ans)