Scribd
Upload
4 views2 pages

Max Substrings Removal from String

The document describes a problem where a character named Meera is trying to remove as many substrings as possible from a main string. It provides constraints on the lengths of the strings and substrings, along with input and output formats. The goal is to determine and print the maximum number of substrings that can be removed from the main string.

Uploaded by

ganeshgaming895
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views2 pages

Max Substrings Removal from String

The document describes a problem where a character named Meera is trying to remove as many substrings as possible from a main string. It provides constraints on the lengths of the strings and substrings, along with input and output formats. The goal is to determine and print the maximum number of substrings that can be removed from the main string.

Uploaded by

ganeshgaming895
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

String Obsession

Who knows the reason for why little Meera is so obsessed with strings and loves to spend her time analyzing them!?

Meera has an everlasting passion for strings. One day, she took a string (let us call it the main string) along with some
substrings and decided to remove as many substrings from the main string as possible. Whenever a part is removed, the
remaining portions of the string are joined together. For example, if the main string is "hello" and "el" is removed, it
becomes "hlo." Note that she can remove one substring only once from the string.

Given the main string and the substrings, determine and print the maximum number of substrings that can be removed.

Constraints
1 <= length of main string <= 55

1 <= length of each substring <= 15

Both main and substrings will be having only lower-case alphabets only.

Input
First line consists of N, denoting the total number of substrings.

Next line consists of N space separated substrings.

Last line consists of the main string.

Output
Print a single integer denoting the maximum number of substrings that can be removed.

Time Limit (secs)


1

Examples
Example 1

Input

hd el llo wor ell lds

helloworlds

Output

Explanation

Given main string is - helloworlds

Remove llo, the string becomes heworlds

Remove wor, the string becomes helds

Remove el, the string becomes hds

Remove hd, the string becomes s. One cannot remove anything further.
Hence the maximum number of substrings we can remove is 4, print 4 as output.

Example 2

Input

ggc rm oo le glh oog ec

googlechrome

Output

Explanation

Given main string is - googlechrome

Remove oo, the string becomes gglechrome

Remove le, the string becomes ggchrome

Remove ggc, the string becomes hrome. One cannot remove anything further.

Second possibility can also be - removing ec,glh,oo resulting in grome, further reduction is impossible. In this case also
only 3 substrings have been removed.

Hence the maximum number of substrings we can remove is 3, hence print 3 as output.

You might also like