Construct String with Minimum Cost (Easy) solution and explanation
11 more videos on this problem
Minimum Cost to Convert String I - Leetcode 2976 - PythonNeetCodeIO · 16:25 · 10K views
3213. Construct String with Minimum Cost | Weekly Leetcode 405codingMohan · 50:55 · 1K views
2027. Minimum Moves to Convert String (Leetcode Easy)Programming Live with Larry · 3:52 · 990 views
3213. Construct String with Minimum Cost (Leetcode Hard)Programming Live with Larry · 43:11 · 846 views
2976. Minimum Cost to Convert String I - Day 27/31 Leetcode July ChallengeProgramming Live with Larry · 11:37 · 551 views
【每日一题】LeetCode 3213. Construct String with Minimum CostHuifeng Guan · 23:35 · 403 views
3213. Construct String with Minimum Cost (leetcode hard)Coder on A Farm · 15:16 · 79 views
Minimum Cost to Convert String I - Leetcode 2976 - JavaCode With K5KC · 11:14 · 68 views
Leetcode Coding Series Problem #2976. Minimum Cost to Convert String I - MEDIUM - Java SolutionSWECODES · 7:00 · 27 views
3213 Construct String with Minimum CostLeetcode and Interview Question · 26:37 · 16 views
leetcode contest 405 3213. Construct String with Minimum Costcomicfans44 · 3:58 · 9 views
Minimum Cost to Convert String I || Leetcode || Easy sol || pyThe learning rabidness · 23:55 · 4 views
The problem
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
iin the range[0, words.length - 1]. - Append
words[i]tos. - 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"tosat a cost of 1, resulting ins = "abc". - Select index 2 and append
"d"tosat a cost of 1, resulting ins = "abcd". - Select index 4 and append
"ef"tosat a cost of 5, resulting ins = "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 <= 20001 <= words.length == costs.length <= 501 <= words[i].length <= target.lengthtargetandwords[i]consist only of lowercase English letters.1 <= costs[i] <= 105
Approach overview
Problem Overview: You are given a target string and a list of words where each word has an associated cost. The task is to construct the target by concatenating words from the list while minimizing the total cost. Words can only match the target at valid positions, so the core challenge is choosing the cheapest sequence of matches that fully builds the string.
Approach 1: Brute Force Backtracking (Exponential Time, O(2^n) time, O(n) space)
The most direct idea is to try constructing the target from left to right. At every index, iterate through every word and check whether it matches the substring starting at that position. If it matches, recursively attempt to build the rest of the string and add the word's cost. This explores every possible combination of word placements. While conceptually simple, repeated exploration of the same suffix makes this approach exponential and impractical for larger inputs.
Approach 2: Dynamic Programming with Substring Checks (O(n * m * L) time, O(n) space)
Dynamic programming avoids recomputation by storing the minimum cost needed to construct the suffix starting at each index. For position i, iterate over all words and check whether each word matches the substring starting at i. If it does, update dp[i] using cost(word) + dp[i + len(word)]. This eliminates repeated work compared to brute force, but still performs many substring comparisons, especially when the word list is large.
Approach 3: Trie + Memoized DFS (Optimal) (O(n * L) time, O(n + totalTrieNodes) space)
The optimized solution stores all words in a Trie. Starting from each index of the target, traverse the Trie character by character while simultaneously scanning the string. Every time a Trie node marks the end of a word, treat it as a valid cut and recursively compute the cost for the remaining suffix. Use memoization to cache the minimum cost for each starting index so each suffix is solved once. Trie traversal avoids checking every word individually and only follows characters that actually match the target. The recursion behaves like a DFS over valid word boundaries while memoization guarantees efficiency.
Recommended for interviews: The Trie + memoized DFS approach is the expected solution. Brute force demonstrates the baseline idea of exploring word placements, but the optimal approach shows you understand prefix structures and dynamic programming to eliminate redundant work. Interviewers typically look for recognizing overlapping subproblems and using a Trie to efficiently match prefixes.
Solution
We first create a Trie trie, where each node in the Trie contains an array children of length 26, and each element in the array is a pointer to the next node. Each node in the Trie also contains a cost variable, which represents the minimum cost from the root node to the current node.
We traverse the words array, inserting each word into the Trie while updating the cost variable for each node.
Next, we define a memoized search function dfs(i), which represents the minimum cost to construct the string starting from target[i]. The answer is dfs(0).
The calculation process of the function dfs(i) is as follows:
- If
i geq len(target), it means the entire string has been constructed, so return0. - Otherwise, we start from the root node of the
trieand traverse all suffixes starting fromtarget[i], finding the minimum cost, which is thecostvariable in thetrie, plus the result ofdfs(j+1), wherejis the ending position of the suffix starting fromtarget[i].
Finally, if dfs(0) < inf, return dfs(0); otherwise, return -1.
The time complexity is O(n^2 + L), and the space complexity is O(n + L). Here, n is the length of target, and L is the sum of the lengths of all words in the words array.
class Trie:
def __init__(self):
self.children: List[Optional[Trie]] = [None] * 26
self.cost = inf
def insert(self, word: str, cost: int):
node = self
for c in word:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.cost = min(node.cost, cost)
class Solution:
def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
@cache
def dfs(i: int) -> int:
if i >= len(target):
return 0
ans = inf
node = trie
for j in range(i, len(target)):
idx = ord(target[j]) - ord("a")
if node.children[idx] is None:
return ans
node = node.children[idx]
ans = min(ans, node.cost + dfs(j + 1))
return ans
trie = Trie()
for word, cost in zip(words, costs):
trie.insert(word, cost)
ans = dfs(0)
return ans if ans < inf else -1class Trie {
public final int inf = 1 << 29;
public Trie[] children = new Trie[26];
public int cost = inf;
public void insert(String word, int cost) {
Trie node = this;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.cost = Math.min(node.cost, cost);
}
}
class Solution {
private Trie trie = new Trie();
private char[] target;
private Integer[] f;
public int minimumCost(String target, String[] words, int[] costs) {
for (int i = 0; i < words.length; ++i) {
trie.insert(words[i], costs[i]);
}
this.target = target.toCharArray();
f = new Integer[target.length()];
int ans = dfs(0);
return ans < trie.inf ? ans : -1;
}
private int dfs(int i) {
if (i >= target.length) {
return 0;
}
if (f[i] != null) {
return f[i];
}
f[i] = trie.inf;
Trie node = trie;
for (int j = i; j < target.length; ++j) {
int idx = target[j] - 'a';
if (node.children[idx] == null) {
return f[i];
}
node = node.children[idx];
f[i] = Math.min(f[i], node.cost + dfs(j + 1));
}
return f[i];
}
}const int inf = 1 << 29;
class Trie {
public:
Trie* children[26]{};
int cost = inf;
void insert(string& word, int cost) {
Trie* node = this;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new Trie();
}
node = node->children[idx];
}
node->cost = min(node->cost, cost);
}
};
class Solution {
public:
int minimumCost(string target, vector<string>& words, vector<int>& costs) {
Trie* trie = new Trie();
for (int i = 0; i < words.size(); ++i) {
trie->insert(words[i], costs[i]);
}
int n = target.length();
int f[n];
memset(f, 0, sizeof(f));
auto dfs = [&](this auto&& dfs, int i) -> int {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
f[i] = inf;
Trie* node = trie;
for (int j = i; j < n; ++j) {
int idx = target[j] - 'a';
if (!node->children[idx]) {
return f[i];
}
node = node->children[idx];
f[i] = min(f[i], node->cost + dfs(j + 1));
}
return f[i];
};
int ans = dfs(0);
return ans < inf ? ans : -1;
}
};const inf = 1 << 29;
class Trie {
children: (Trie | null)[];
cost: number;
constructor() {
this.children = Array(26).fill(null);
this.cost = inf;
}
insert(word: string, cost: number): void {
let node: Trie = this;
for (const c of word) {
const idx = c.charCodeAt(0) - 97;
if (!node.children[idx]) {
node.children[idx] = new Trie();
}
node = node.children[idx]!;
}
node.cost = Math.min(node.cost, cost);
}
}
function minimumCost(target: string, words: string[], costs: number[]): number {
const trie = new Trie();
for (let i = 0; i < words.length; ++i) {
trie.insert(words[i], costs[i]);
}
const n = target.length;
const f: number[] = Array(n).fill(0);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
f[i] = inf;
let node: Trie | null = trie;
for (let j = i; j < n; ++j) {
const idx = target.charCodeAt(j) - 97;
if (!node?.children[idx]) {
return f[i];
}
node = node.children[idx];
f[i] = Math.min(f[i], node!.cost + dfs(j + 1));
}
return f[i];
};
const ans = dfs(0);
return ans < inf ? ans : -1;
}const inf = 1 << 29
type Trie struct {
children [26]*Trie
cost int
}
func NewTrie() *Trie {
return &Trie{cost: inf}
}
func (t *Trie) insert(word string, cost int) {
node := t
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = NewTrie()
}
node = node.children[idx]
}
node.cost = min(node.cost, cost)
}
func minimumCost(target string, words []string, costs []int) int {
trie := NewTrie()
for i, word := range words {
trie.insert(word, costs[i])
}
n := len(target)
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != 0 {
return f[i]
}
f[i] = inf
node := trie
for j := i; j < n; j++ {
idx := target[j] - 'a'
if node.children[idx] == nil {
return f[i]
}
node = node.children[idx]
f[i] = min(f[i], node.cost+dfs(j+1))
}
return f[i]
}
if ans := dfs(0); ans < inf {
return ans
}
return -1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Backtracking | O(2^n) | O(n) | Conceptual starting point or very small inputs |
| Dynamic Programming with Substring Checks | O(n * m * L) | O(n) | When word list is small and substring checks are cheap |
| Trie + Memoized DFS | O(n * L) | O(n + Trie) | General case with many words and shared prefixes |
Frequently asked questions
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).