Form The String

Hard

0/120

0 upvote

Problem statement

Sara has a main string and a list of N available substrings, each with an associated cost. Her goal is to construct the main string by concatenating some of the available substrings, aiming for the minimum possible total cost.

The rules are as follows:

1) Cost: The total cost is the sum of the costs of all substrings used. Each substring can be used multiple times, and its cost is incurred each time it's used.

2) Validity: A substring from the list can only be used if it is a substring of the main string.

3) Overlap: When concatenating, substrings can overlap. For example, to form "adkmu", using "adkm" (cost 1) and "kmu" (cost 2) is a valid strategy. The concatenation "adkmkmu" can be reduced to "adkmu" by removing the overlapping part. The total cost is simply the sum of the costs of the chosen substrings (1 + 2 = 3).

Your task is to help Sara find the minimum cost to construct the entire main string. If it's impossible to form the main string with the given substrings, you should report it.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer N, the number of available substrings.

The next N lines each contain a substring and its cost, separated by a space.

The final line contains the main string.

Output Format:

Print a single integer representing the minimum cost.

If it is impossible to form the main string, print "Impossible".

Note:

This problem can be solved efficiently using dynamic programming. Let dp[i] be the minimum cost to form the prefix of the main string of length i. The goal is to compute dp[length of main string].

Sample Input 1:

10
evi 8
vta 9
co 1
dev 5
vit 6
odv 2
d 3
de 4
itaa 1
a 7
codevita

Sample Output 1:

Explanation for Sample 1:

The optimal way to form "codevita" is by using the substrings:
  co (cost 1) -> forms "co"
  de (cost 4) -> forms "code"
  vit (cost 6) -> forms "codevit"
  a (cost 7) -> forms "codevita"
Total cost = 1 + 4 + 6 + 7 = 18.

Expected Time Complexity:

The expected time complexity is O(N^3).

Constraints:

1 <= length of main string <= 50
1 <= N <= 100
1 <= cost of each substring <= 100
length of each substring <= length of main string
All strings consist of lowercase English letters.

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Form The String

Console