Is Construct String with Minimum Cost easy or hard?

Construct String with Minimum Cost is classified as Hard because it combines dynamic programming with efficient string matching. The challenge lies in designing the correct DP state and avoiding expensive substring checks when the word list becomes large.

Construct String with Minimum Cost Python/Java solution

Python implementations typically use top-down recursion with memoization or bottom-up DP arrays. Java solutions often use iterative DP for performance and clarity. Both implementations follow the same transition rule: if a word matches at position i, update dp[i + len(word)] with dp[i] + cost.

How to solve Construct String with Minimum Cost in O(n)?

A pure O(n) solution is generally not achievable because each position may need to consider multiple candidate words. However, preprocessing techniques like tries, rolling hash, or suffix arrays can reduce substring matching overhead, bringing the complexity closer to O(n log n + matches) while keeping DP transitions efficient.

What is the best approach for Construct String with Minimum Cost?

Dynamic programming with prefix states is the most practical approach. Define dp[i] as the minimum cost to build the first i characters of the target and transition using words that match at position i. This reduces the problem to O(n * m * L) time with O(n) space, where m is the number of words and L is the average word length.

Is Construct String with Minimum Cost asked at Google/Amazon/Meta?

Hard dynamic programming and string construction problems similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. They test the ability to design DP states, optimize string matching, and reason about time complexity tradeoffs.

What data structure is used in Construct String with Minimum Cost?

The core solution uses dynamic programming with arrays or memoization tables. For optimization, developers often combine DP with string data structures such as tries, hash maps, or suffix arrays to accelerate substring matching.

What is the time complexity of Construct String with Minimum Cost?

The standard dynamic programming solution runs in O(n * m * L) time. For each position in the target string (n), the algorithm checks all words (m) and verifies substring matches that take up to L time. Space complexity is O(n) for the DP array or memo table.

Description Hints 1 Solution Video 35:28

3213. Construct String with Minimum Cost

Hard19.0% acceptance1 company

You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.

Imagine an empty string s.

You can perform the following operation any number of times (including zero):

Choose an index i in the range [0, words.length - 1].
Append words[i] to s.
The cost of operation is costs[i].

Return the minimum cost to make s equal to target. If it's not possible, return -1.

Example 1:

Input: target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

Output: 7

Explanation:

The minimum cost can be achieved by performing the following operations:

Select index 1 and append "abc" to s at a cost of 1, resulting in s = "abc".
Select index 2 and append "d" to s at a cost of 1, resulting in s = "abcd".
Select index 4 and append "ef" to s at a cost of 5, resulting in s = "abcdef".

Example 2:

Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

Output: -1

Explanation:

It is impossible to make s equal to target, so we return -1.

Constraints:

1 <= target.length <= 5 * 10⁴
1 <= words.length == costs.length <= 5 * 10⁴
1 <= words[i].length <= target.length
The total sum of words[i].length is less than or equal to 5 * 10⁴.
target and words[i] consist only of lowercase English letters.
1 <= costs[i] <= 10⁴

Asked at 1 company

Mitsogo

Topics

Hints open one at a time

Hint 1

Use Dynamic Programming along with Aho-Corasick or Hashing.

35:28

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution