Is Construct String with Minimum Cost (Easy) easy or hard?

Despite the "Easy" label in the title, the problem is typically rated Medium because it combines Trie construction with dynamic programming or memoized search. The difficulty comes from recognizing overlapping subproblems and optimizing prefix matching.

Construct String with Minimum Cost (Easy) Python/Java solution

Most implementations build a Trie from the word list and perform a DFS with memoization over the target string indices. The same logic translates cleanly across Python, Java, C++, Go, and TypeScript: traverse the Trie while scanning the string and update the minimum cost using cached results.

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

Pure O(n) is not typically achievable because prefix matching requires scanning characters. The closest practical bound is O(n * L) using a Trie. Starting from each index, traverse the Trie while matching characters in the target string and compute the minimum cost using memoized recursion.

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

Trie with memoized DFS is the most efficient approach. Insert all words into a Trie, then recursively build the target string while traversing the Trie to find matching prefixes. Memoization stores the minimum cost for each starting index so each suffix is computed once. This reduces the time complexity to roughly O(n * L), where L is the maximum word length.

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

Problems involving Trie + dynamic programming combinations frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of string construction, word break optimization, and minimum-cost segmentation are common interview patterns.

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

The key data structure is a Trie for efficient prefix matching. It is combined with dynamic programming or memoized DFS to store the minimum cost for each index of the target string. This pairing avoids repeated substring scans and redundant recursion.

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

The optimal Trie + memoization solution runs in O(n * L) time where n is the length of the target string and L is the maximum word length. Each index of the target is processed once, and Trie traversal limits comparisons to matching prefixes. Space complexity is O(n + total Trie nodes).

Description Hints 2 Solution Video 16:25

3253. Construct String with Minimum Cost (Easy)

Medium58.8% acceptancePremium elsewhere, free here

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 <= 2000
1 <= words.length == costs.length <= 50
1 <= words[i].length <= target.length
target and words[i] consist only of lowercase English letters.
1 <= costs[i] <= 10⁵

Hints open one at a time

Hint 1

Let dp[i] denote the minimum cost to make s equal to the prefix of target of length i.

Hint 2

dp[i] = min(costs[k] + dp[j]), where j > i and words[k] == target[i..j].

16:25

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"abcdef"
["abdef","abc","d","def","ef"]
[100,1,1,10,5]

Input

"aaaa"
["z","zz","zzz"]
[1,10,100]

Your code is saved on this device.Solution