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):
i in the range [0, words.length - 1].words[i] to s.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:
"abc" to s at a cost of 1, resulting in s = "abc"."d" to s at a cost of 1, resulting in s = "abcd"."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 * 1041 <= words.length == costs.length <= 5 * 1041 <= words[i].length <= target.lengthwords[i].length is less than or equal to 5 * 104.target and words[i] consist only of lowercase English letters.1 <= costs[i] <= 104Problem Overview: You are given a target string and a list of words where each word has an associated cost. The goal is to construct the entire target string by concatenating these words so that the total cost is minimized. Each word can be used multiple times, but it must exactly match the portion of the target where it is placed.
Approach 1: Backtracking with Memoization (Exponential → O(n * m * L))
Start from index 0 in the target and recursively try every word that matches the current position. If a word matches, move the pointer forward by its length and add its cost. Without optimization this explores an exponential number of combinations. Memoization stores the minimum cost for each starting index so repeated states are computed once. Time complexity becomes roughly O(n * m * L), where n is the target length, m the number of words, and L the average word length. Space complexity is O(n) for recursion and memo storage.
Approach 2: Dynamic Programming with Word Matching (O(n * m * L))
Define dp[i] as the minimum cost required to construct the prefix target[0..i). Initialize dp[0] = 0. For every position i, iterate through the word list and check whether a word matches the substring starting at i. If it matches, update dp[i + len(word)] = min(dp[i + len(word)], dp[i] + cost). This transforms the search into a forward state transition similar to classic Dynamic Programming. Time complexity is O(n * m * L) due to substring comparisons. Space complexity is O(n).
Approach 3: Top-Down Dynamic Programming with Memoization (O(n * m * L))
This version expresses the same recurrence using recursion. The function dfs(i) returns the minimum cost to build the suffix starting at index i. For every word that matches target[i : i + len(word)], recursively compute dfs(i + len(word)) and add the cost. Memoization avoids recomputing states. The algorithm still performs substring checks, so the complexity remains O(n * m * L) with O(n) space. The approach fits naturally when reasoning about suffix construction and is common in problems combining String processing with Dynamic Programming.
Approach 4: Optimized Matching with Suffix Structures (Up to O(n log n + matches))
When the word list is large, repeated substring comparisons dominate runtime. Preprocessing the target using structures like a Suffix Array, trie, or hashing allows faster substring checks. Instead of scanning every word at every position, you query which words match the current suffix and only transition those states. The DP structure stays the same but matching becomes significantly faster for large datasets.
Recommended for interviews: The bottom-up dynamic programming solution with word matching is usually expected. It clearly shows you understand state transitions and optimal substructure. Mentioning memoized recursion demonstrates the same idea from another direction, while discussing suffix-based optimization shows awareness of scaling constraints for large inputs.
In this approach, we use dynamic programming with memoization to minimize the cost of building the target string by selecting parts of words. We define a dp function that represents the minimum cost to build the substring of the target from a starting index to the end of the string. This function checks possible word matches at different starting positions and calculates the cost recursively.
The Python solution uses a recursive dynamic programming approach, utilizing memoization to store results of previously calculated indices to minimize recomputation. The dp function computes the minimal cost required to construct the target string from the current index to the end. It iterates over all words to see if they match the current segment of the target string. If they match, it calculates the cost recursively for the rest of the string. The base case occurs when the index equals the target's length, returning zero cost because no additional construction is needed.
Python
Time Complexity: O(N * M * L), where N is the length of the target string, M is the number of words, and L is the average length of a word. Space Complexity: O(N), where N is the length of the target string due to memoization.
This approach structures the solution using a bottom-up dynamic programming table (or list) that builds from the smallest subproblem to the full solution. The idea is to fill a dp array where each entry dp[i] represents the minimum cost to build the target's substring from index 0 to i. The solution iteratively checks each word and updates the dp array whenever a word's substring matches a segment of the target starting from an earlier index.
The Java solution uses a bottom-up dynamic programming approach. It initializes a dp array where dp[i] is the minimum cost to reach the ith character of the target. It iteratively updates this array using matching words from the 'words' array to segments of the target. Each iteration checks if a word can extend the current prefix of the target and updates the dp array accordingly. If the whole target string can be constructed, it returns dp[n] as the minimum cost, otherwise, it returns -1.
Java
Time Complexity: O(N * M * L), where N is the length of the target string, M is the number of words, and L is the average length of a word. Space Complexity: O(N), where N is the length of the target string due to the dp array.
This approach leverages dynamic programming to solve the problem by matching prefixes of the target string with dictionary words.
The main idea is to maintain a dp array where dp[i] represents the minimum cost to form the first i characters of the target string. We iterate over each character of the target, and for each position, we attempt to match it with every possible word from the words array. If a word matches a substring of the target beginning at position i, we update dp[i + len(word)] to be the minimum of its current value and dp[i] + cost associated with the word.
The challenge in this approach is efficiently verifying matches between words in the words array and substrings in the target string.
The C solution uses dynamic programming to maintain the minimum cost to form up to each length of the target string. We initialize a dp array with infinity (or a very large value), indicating that those lengths are unreachable initially. At dp[0], we set it to 0 because the cost to form an empty string is zero.
We then iterate over the dp array, updating each entry by attempting to extend it with each word in the words array. If a word matches a substring starting from the current dp index in the target, we update the corresponding dp value to the minimum cost necessary to reach that position using this word or others before it.
Using constraints wisely helps ensure optimal run-time even with relatively longer strings.
Time Complexity: O(T * W * L), where T is the length of the target, W is the size of the words array, and L is the average length of words.
Space Complexity: O(T), for storing the dynamic programming array.
This approach employs backtracking enhanced with memoization to solve subproblems efficiently by caching previously computed results.
The idea here is to explore forming the target string starting from each index using a recursive backtracking function. We attempt to match every word from the words array at the current starting index. If a match is found, the function is recursively called to find the minimum cost from the end of this match to the end of the target.
Memoization ensures that for each starting index, we do not recompute previously explored minimal costs, thus reducing computational overhead.
The C solution uses a recursion function with memoization to attempt constructing the target string starting from each index. The memo array stores the minimum cost required for substrings beginning at various indexes, preventing redundant computations.
The recursion checks each word in words[] against the current index in target, and if found, recurs into forming the rest of the string. Updating the memoization on returning from recursion ensures efficient caching.
Time Complexity: O(T * W * L), where T is the length of the target, W is the number of words, L is the average length of words. Different due to recursion depth and cache misses.
Space Complexity: O(T), due to memo array storage.
We define f[i] as the minimum cost to construct the first i characters of target, with the initial condition f[0] = 0 and all other values set to infinity. The answer is f[n], where n is the length of target.
For the current f[i], consider enumerating the length j of the word. If j leq i, then we can consider the hash value of the segment from i - j + 1 to i. If this hash value corresponds to an existing word, then we can transition from f[i - j] to f[i]. The state transition equation is as follows:
$
f[i] = min(f[i], f[i - j] + cost[k])
where cost[k] represents the minimum cost of a word of length j whose hash value matches target[i - j + 1, i].
The time complexity is O(n times \sqrt{L}), and the space complexity is O(n). Here, n is the length of target, and L is the sum of the lengths of all words in the array words$.
| Approach | Complexity |
|---|---|
| Dynamic Programming - Top-Down with Memoization | Time Complexity: O(N * M * L), where N is the length of the target string, M is the number of words, and L is the average length of a word. Space Complexity: O(N), where N is the length of the target string due to memoization. |
| Bottom-Up Dynamic Programming | Time Complexity: O(N * M * L), where N is the length of the target string, M is the number of words, and L is the average length of a word. Space Complexity: O(N), where N is the length of the target string due to the dp array. |
| Approach 1: Dynamic Programming with Word Matching | Time Complexity: O(T * W * L), where T is the length of the target, W is the size of the words array, and L is the average length of words. Space Complexity: O(T), for storing the dynamic programming array. |
| Approach 2: Backtracking with Memoization | Time Complexity: O(T * W * L), where T is the length of the target, W is the number of words, L is the average length of words. Different due to recursion depth and cache misses. Space Complexity: O(T), due to memo array storage. |
| String Hashing + Dynamic Programming + Enumerating Length | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Memoization | O(n * m * L) | O(n) | When exploring combinations conceptually before converting to iterative DP |
| Top-Down Dynamic Programming | O(n * m * L) | O(n) | Natural recursive reasoning for suffix construction |
| Bottom-Up Dynamic Programming | O(n * m * L) | O(n) | Standard interview solution and easiest to implement iteratively |
| DP with Optimized Matching (Suffix Array/Trie) | O(n log n + matches) | O(n + totalWordLength) | Large word lists where repeated substring comparisons are expensive |
3213. Construct String with Minimum Cost | DP + Trie | ! Aho-Corasick Algorithm Explanation • Aryan Mittal • 3,977 views views
Watch 7 more video solutions →Practice Construct String with Minimum Cost with our built-in code editor and test cases.
Practice on FleetCode