Construct String with Minimum Cost solution and explanation
6 more videos on this problem
3213. Construct String with Minimum Cost | DP + Trie | ! Aho-Corasick Algorithm ExplanationAryan Mittal · 35:28 · 4K views
3213. Construct String with Minimum Cost | Weekly Leetcode 405codingMohan · 50:55 · 1K views
3213. Construct String with Minimum Cost | Leetcode Weekly Contest 7 July 2024 | Hard | Trie + DPAlgorithmHQ · 22:59 · 989 views
3213. Construct String with Minimum Cost (Leetcode Hard)Programming Live with Larry · 43:11 · 906 views
【每日一题】LeetCode 3213. Construct String with Minimum CostHuifeng Guan · 23:35 · 441 views
3213. Construct String with Minimum Cost | Weekly Leetcode 405 | Trie + DPAmit Dhyani · 36:58 · 367 views
3213. Construct String with Minimum Cost (leetcode hard)Coder on A Farm · 15:16 · 96 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 <= 5 * 1041 <= words.length == costs.length <= 5 * 1041 <= words[i].length <= target.length- The total sum of
words[i].lengthis less than or equal to5 * 104. targetandwords[i]consist only of lowercase English letters.1 <= costs[i] <= 104
Approach overview
Problem 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.
Approach 1: Dynamic Programming - Top-Down with Memoization
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.
def minCost(target, words, costs):
memo = {}
def dp(index):
if index == len(target):
return 0
if index in memo:
return memo[index]
min_cost = float('inf')
for i, word in enumerate(words):
length_word = len(word)
if target[index:index + length_word] == word:
current_cost = costs[i] + dp(index + length_word)
min_cost = min(min_cost, current_cost)
memo[index] = min_cost if min_cost != float('inf') else -1
return memo[index]
result = dp(0)
return result if result != float('inf') else -1The 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.
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.
Approach 2: Bottom-Up Dynamic Programming
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.
import java.util.Arrays;
public int minCost(String target, String[] words, int[] costs) {
int n = target.length();
Integer[] dp = new Integer[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
if (dp[i] == Integer.MAX_VALUE) continue;
for (int j = 0; j < words.length; ++j) {
int lengthWord = words[j].length();
if (i + lengthWord <= n && target.substring(i, i + lengthWord).equals(words[j])) {
dp[i + lengthWord] = Math.min(dp[i + lengthWord], dp[i] + costs[j]);
}
}
}
return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}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.
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 3: Approach 1: Dynamic Programming with Word Matching
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.
def min_cost_to_construct_string(target, words, costs):
n = len(target)
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(n):
if dp[i] == float('inf'):
continue
for j in range(len(words)):
len_word = len(words[j])
if i + len_word <= n and target[i:i + len_word] == words[j]:
dp[i + len_word] = min(dp[i + len_word], dp[i] + costs[j])
return -1 if dp[n] == float('inf') else dp[n]
# Example usage:
target = "abcdef"
words = ["abdef", "abc", "d", "def", "ef"]
costs = [100, 1, 1, 10, 5]
print(min_cost_to_construct_string(target, words, costs))import java.util.*;
public class MinCostToConstruct {
public static int minCostToConstructString(String target, String[] words, int[] costs) {
int n = target.length();
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == Integer.MAX_VALUE) continue;
for (int j = 0; j < words.length; j++) {
String word = words[j];
int len = word.length();
if (i + len <= n && target.substring(i, i + len).equals(word)) {
dp[i + len] = Math.min(dp[i + len], dp[i] + costs[j]);
}
}
}
return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}
public static void main(String[] args) {
String target = "abcdef";
String[] words = {"abdef", "abc", "d", "def", "ef"};
int[] costs = {100, 1, 1, 10, 5};
System.out.println(minCostToConstructString(target, words, costs));
}
}#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int minCostToConstructString(string target, vector<string>& words, vector<int>& costs) {
int targetLen = target.size();
vector<int> dp(targetLen + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < targetLen; ++i) {
if (dp[i] == INT_MAX) continue;
for (int j = 0; j < words.size(); ++j) {
int wordLen = words[j].size();
if (i + wordLen <= targetLen && target.substr(i, wordLen) == words[j]) {
dp[i + wordLen] = min(dp[i + wordLen], dp[i] + costs[j]);
}
}
}
return dp[targetLen] == INT_MAX ? -1 : dp[targetLen];
}
int main() {
string target = "abcdef";
vector<string> words = {"abdef", "abc", "d", "def", "ef"};
vector<int> costs = {100, 1, 1, 10, 5};
cout << minCostToConstructString(target, words, costs) << endl;
return 0;
}function minCostToConstructString(target, words, costs) {
const n = target.length;
const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i < n; i++) {
if (dp[i] === Infinity) continue;
for (let j = 0; j < words.length; j++) {
const lenWord = words[j].length;
if (i + lenWord <= n && target.substr(i, lenWord) === words[j]) {
dp[i + lenWord] = Math.min(dp[i + lenWord], dp[i] + costs[j]);
}
}
}
return dp[n] === Infinity ? -1 : dp[n];
}
// Example usage:
const target = "abcdef";
const words = ["abdef", "abc", "d", "def", "ef"];
const costs = [100, 1, 1, 10, 5];
console.log(minCostToConstructString(target, words, costs));#include <stdio.h>
#include <string.h>
#include <limits.h>
int minCostToForm(char* target, char** words, int* costs, int wordsSize) {
int targetLen = strlen(target);
int dp[targetLen + 1];
for (int i = 0; i <= targetLen; i++) dp[i] = INT_MAX;
dp[0] = 0;
for (int i = 0; i < targetLen; i++) {
if (dp[i] == INT_MAX) continue;
for (int j = 0; j < wordsSize; j++) {
int wordLen = strlen(words[j]);
if (i + wordLen <= targetLen && strncmp(target + i, words[j], wordLen) == 0) {
dp[i + wordLen] = fmin(dp[i + wordLen], dp[i] + costs[j]);
}
}
}
return dp[targetLen] == INT_MAX ? -1 : dp[targetLen];
}
int main() {
char* target = "abcdef";
char* words[] = {"abdef", "abc", "d", "def", "ef"};
int costs[] = {100, 1, 1, 10, 5};
int minCost = minCostToForm(target, words, costs, 5);
printf("%d\n", minCost);
return 0;
}using System;
class MinCostToConstruct {
public static int MinCostToConstructString(string target, string[] words, int[] costs) {
int n = target.Length;
int[] dp = new int[n + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == int.MaxValue) continue;
for (int j = 0; j < words.Length; j++) {
int lenWord = words[j].Length;
if (i + lenWord <= n && target.Substring(i, lenWord) == words[j]) {
dp[i + lenWord] = Math.Min(dp[i + lenWord], dp[i] + costs[j]);
}
}
}
return dp[n] == int.MaxValue ? -1 : dp[n];
}
public static void Main(string[] args) {
string target = "abcdef";
string[] words = { "abdef", "abc", "d", "def", "ef" };
int[] costs = { 100, 1, 1, 10, 5 };
Console.WriteLine(MinCostToConstructString(target, words, costs));
}
}The Python solution adopts list comprehension for initial DP setup. We maintain a dp array in which dp[i] is the minimum cost to form the target string up to the ith character. We iterate through the target, attempting matches with entries in the words list.
In Python, simple slicing checks for matching and list operations help handle constraints efficiently.
Time Complexity: O(T * W * L), similar to other approaches.
Space Complexity: O(T), for list storage.
Approach 4: Approach 2: Backtracking with Memoization
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.
def min_cost_to_construct(target, words, costs):
n = len(target)
memo = [-1] * (n + 1)
def helper(start):
if start == n:
return 0
if memo[start] != -1:
return memo[start]
min_cost = float('inf')
for i in range(len(words)):
len_word = len(words[i])
if start + len_word <= n and target[start:start + len_word] == words[i]:
cost = helper(start + len_word)
if cost != float('inf'):
min_cost = min(min_cost, cost + costs[i])
memo[start] = min_cost
return min_cost
result = helper(0)
return -1 if result == float('inf') else result
# Example usage:
target = "abcdef"
words = ["abdef", "abc", "d", "def", "ef"]
costs = [100, 1, 1, 10, 5]
print(min_cost_to_construct(target, words, costs))import java.util.*;
public class MinCostConstructWithRecursion {
private static int[] memo;
private static int minCostRec(String target, String[] words, int[] costs, int start) {
if (start == target.length()) return 0;
if (memo[start] != -1) return memo[start];
int minCost = Integer.MAX_VALUE;
for (int i = 0; i < words.length; i++) {
int len = words[i].length();
if (start + len <= target.length() && target.substring(start, start + len).equals(words[i])) {
int cost = minCostRec(target, words, costs, start + len);
if (cost != Integer.MAX_VALUE) minCost = Math.min(minCost, cost + costs[i]);
}
}
return memo[start] = minCost;
}
public static int minCostToConstructString(String target, String[] words, int[] costs) {
memo = new int[target.length()];
Arrays.fill(memo, -1);
int result = minCostRec(target, words, costs, 0);
return result == Integer.MAX_VALUE ? -1 : result;
}
public static void main(String[] args) {
String target = "abcdef";
String[] words = {"abdef", "abc", "d", "def", "ef"};
int[] costs = {100, 1, 1, 10, 5};
System.out.println(minCostToConstructString(target, words, costs));
}
}#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
vector<int> memo;
int minCostRec(const string& target, const vector<string>& words, const vector<int>& costs, int start) {
int n = target.size();
if (start == n) return 0;
if (memo[start] != -1) return memo[start];
int minCost = INT_MAX;
for (int i = 0; i < words.size(); i++) {
int lenWord = words[i].size();
if (start + lenWord <= n && target.substr(start, lenWord) == words[i]) {
int cost = minCostRec(target, words, costs, start + lenWord);
if (cost != INT_MAX) minCost = min(minCost, cost + costs[i]);
}
}
memo[start] = minCost;
return minCost;
}
int minCostToConstruct(const string& target, vector<string>& words, vector<int>& costs) {
memo.assign(target.size() + 1, -1);
int minCost = minCostRec(target, words, costs, 0);
return minCost == INT_MAX ? -1 : minCost;
}
int main() {
string target = "abcdef";
vector<string> words = {"abdef", "abc", "d", "def", "ef"};
vector<int> costs = {100, 1, 1, 10, 5};
cout << minCostToConstruct(target, words, costs) << endl;
return 0;
}function minCostToConstruct(target, words, costs) {
const n = target.length;
const memo = new Array(n + 1).fill(-1);
function helper(start) {
if (start === n) return 0;
if (memo[start] !== -1) return memo[start];
let minCost = Infinity;
for (let i = 0; i < words.length; i++) {
const wordLen = words[i].length;
if (start + wordLen <= n && target.substr(start, wordLen) === words[i]) {
const cost = helper(start + wordLen);
if (cost !== Infinity) {
minCost = Math.min(minCost, cost + costs[i]);
}
}
}
memo[start] = minCost;
return minCost;
}
const result = helper(0);
return result === Infinity ? -1 : result;
}
// Example usage:
const target = "abcdef";
const words = ["abdef", "abc", "d", "def", "ef"];
const costs = [100, 1, 1, 10, 5];
console.log(minCostToConstruct(target, words, costs));#include <stdio.h>
#include <string.h>
#include <limits.h>
int memo[50001];
int minCostRec(char* target, char** words, int* costs, int wordsSize, int start, int* memo) {
int targetLen = strlen(target);
if (start == targetLen) return 0;
if (memo[start] != -1) return memo[start];
int minCost = INT_MAX;
for (int i = 0; i < wordsSize; i++) {
int wordLen = strlen(words[i]);
if (start + wordLen <= targetLen && strncmp(target + start, words[i], wordLen) == 0) {
int cost = minCostRec(target, words, costs, wordsSize, start + wordLen, memo);
if (cost != INT_MAX) minCost = fmin(minCost, cost + costs[i]);
}
}
memo[start] = minCost;
return minCost;
}
int minCostToFormByBacktracking(char* target, char** words, int* costs, int wordsSize) {
memset(memo, -1, sizeof(memo));
int minCost = minCostRec(target, words, costs, wordsSize, 0, memo);
return minCost == INT_MAX ? -1 : minCost;
}
int main() {
char* target = "abcdef";
char* words[] = {"abdef", "abc", "d", "def", "ef"};
int costs[] = {100, 1, 1, 10, 5};
int minCost = minCostToFormByBacktracking(target, words, costs, 5);
printf("%d\n", minCost);
return 0;
}using System;
class MinCostConstructWithRecursion {
private static int[] memo;
private static int MinCostRec(string target, string[] words, int[] costs, int start) {
if (start == target.Length) return 0;
if (memo[start] != -1) return memo[start];
int minCost = int.MaxValue;
for (int i = 0; i < words.Length; i++) {
int len = words[i].Length;
if (start + len <= target.Length && target.Substring(start, len) == words[i]) {
int cost = MinCostRec(target, words, costs, start + len);
if (cost != int.MaxValue) minCost = Math.Min(minCost, cost + costs[i]);
}
}
return memo[start] = minCost;
}
public static int MinCostToConstructString(string target, string[] words, int[] costs) {
memo = new int[target.Length + 1];
Array.Fill(memo, -1);
int result = MinCostRec(target, words, costs, 0);
return result == int.MaxValue ? -1 : result;
}
public static void Main(string[] args) {
string target = "abcdef";
string[] words = { "abdef", "abc", "d", "def", "ef" };
int[] costs = { 100, 1, 1, 10, 5 };
Console.WriteLine(MinCostToConstructString(target, words, costs));
}
}In Python, this approach adopts recursive backtracking to determine the minimum cost efficiently via memoization. The helper function acts recursively on each target start position, testing against all possible words while leveraging stored results for speed.
Slicing and recursion pair effectively ensure relatively simple logic despite underlying complexity.
Time Complexity: O(T * W * L), influenced by recursion and dynamic data caching.
Space Complexity: O(T), for memoization purposes.
Approach 5: String Hashing + Dynamic Programming + Enumerating Length
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$.
type Hashing struct {
p []int64
h []int64
mod int64
}
func NewHashing(word string, base, mod int64) *Hashing {
n := len(word)
p := make([]int64, n+1)
h := make([]int64, n+1)
p[0] = 1
for i := 1; i <= n; i++ {
p[i] = p[i-1] * base % mod
h[i] = (h[i-1]*base + int64(word[i-1])) % mod
}
return &Hashing{p, h, mod}
}
func (hs *Hashing) query(l, r int) int64 {
return (hs.h[r] - hs.h[l-1]*hs.p[r-l+1]%hs.mod + hs.mod) % hs.mod
}
func minimumCost(target string, words []string, costs []int) int {
const base = 13331
const mod = 998244353
const inf = math.MaxInt32 / 2
n := len(target)
hashing := NewHashing(target, base, mod)
f := make([]int, n+1)
for i := range f {
f[i] = inf
}
f[0] = 0
ss := make(map[int]struct{})
for _, w := range words {
ss[len(w)] = struct{}{}
}
lengths := make([]int, 0, len(ss))
for length := range ss {
lengths = append(lengths, length)
}
sort.Ints(lengths)
d := make(map[int64]int)
for i, w := range words {
var x int64
for _, c := range w {
x = (x*base + int64(c)) % mod
}
if existingCost, exists := d[x]; exists {
if costs[i] < existingCost {
d[x] = costs[i]
}
} else {
d[x] = costs[i]
}
}
for i := 1; i <= n; i++ {
for _, j := range lengths {
if j > i {
break
}
x := hashing.query(i-j+1, i)
if cost, ok := d[x]; ok {
f[i] = min(f[i], f[i-j]+cost)
}
}
}
if f[n] >= inf {
return -1
}
return f[n]
}Complexity comparison
| 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), similar to other approaches. Space Complexity: O(T), for list storage. |
| Approach 2: Backtracking with Memoization | Time Complexity: O(T * W * L), influenced by recursion and dynamic data caching. Space Complexity: O(T), for memoization purposes. |
| String Hashing + Dynamic Programming + Enumerating Length | – |
Complexity analysis
| 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 |
Frequently asked questions
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.