Construct String with Minimum Cost
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem. We define dp[i] as the minimum cost to build the prefix of target of length i. The base case is dp[0] = 0. To compute dp[i], we consider all possible last words that could form this prefix. If target.substring(j, i) matches a word w from the words array, we can potentially transition from a previously computed state dp[j]. The cost would be dp[j] plus the cost of w. We take the minimum over all such possibilities.
Algorithm
- Define a DP array
dpof sizen+1, wherenis the length oftarget.dp[i]will store the minimum cost to construct the prefixtarget.substring(0, i). - Initialize
dp[0] = 0(cost to build an empty string is zero) and all otherdp[i]to infinity. - Iterate through each possible end position
iof a prefix, from 1 ton. - For each
i, iterate through each possible start positionjfrom 0 toi-1. - Extract the substring
sub = target.substring(j, i). - Iterate through the entire
wordsarray. Ifsubmatches awords[k], it represents a valid move. - If a match is found, update
dp[i]with the minimum cost:dp[i] = min(dp[i], dp[j] + costs[k]). - After filling the
dparray,dp[n]contains the minimum cost for the entiretargetstring. Ifdp[n]is still infinity, it's impossible to form the target, so return -1.
Walkthrough
The state transition for this DP approach is as follows:
dp[i] = min(dp[j] + cost(word)) for all 0 <= j < i where target.substring(j, i) is a word in the words array.
To implement this, we can use three nested loops. The outer loop iterates i from 1 to n. The second loop iterates j from 0 to i-1. The innermost loop iterates through all the words in the words array to check if target.substring(j, i) is a match. This leads to a very high time complexity.
import java.util.Arrays; class Solution { public int minimumCost(String target, String[] words, int[] costs) { int n = target.length(); long[] dp = new long[n + 1]; Arrays.fill(dp, Long.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { String sub = target.substring(j, i); for (int k = 0; k < words.length; k++) { if (sub.equals(words[k])) { if (dp[j] != Long.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + costs[k]); } } } } } return dp[n] == Long.MAX_VALUE ? -1 : (int) dp[n]; }}To slightly optimize, we can pre-process the words and costs into a HashMap for O(1) average time lookups. However, the complexity is still dominated by the two loops over the target string's length and the substring operation, resulting in an O(n^3) complexity, which is too slow.
Complexity
Time
O(n^2 * m * l), where `n` is `target.length`, `m` is `words.length`, and `l` is the average word length. This is because of the loops for `i` (n), `j` (n), `k` (m), and string comparison (l).
Space
O(n) for the DP array.
Trade-offs
Pros
Simple to understand and implement.
Correctly models the problem as a shortest path on a DAG.
Cons
Extremely inefficient due to multiple nested loops.
Repeatedly scans the
wordsarray.Substring operations inside loops are costly.
Will time out for the given constraints.
This approach improves upon the naive DP by optimizing the search for matching words. Instead of scanning the entire words array for every substring, we use a Trie. By building a Trie on the reversed words, we can efficiently check all suffixes of target.substring(0, i) for matches in a single pass backwards from index i-1. For each i, we traverse from target[i-1] down to target[0], and simultaneously traverse the Trie. If we find a word in the Trie, we use its cost and the corresponding dp[j] value to update dp[i].
Algorithm
- Pre-process the
wordsandcoststo handle duplicate words. Store each unique word and its minimum cost in a map. Then, build a Trie (prefix tree) using the reversed versions of these unique words. Each node in the Trie that marks the end of a reversed word will store its corresponding minimum cost. - Define a DP array
dpof sizen+1, wheredp[i]stores the minimum cost to buildtarget.substring(0, i). - Initialize
dp[0] = 0and all otherdp[i]to infinity. - Iterate
ifrom 1 ton. To computedp[i], we look for words in our dictionary that are suffixes oftarget.substring(0, i). - For each
i, traverse backwards fromtarget.charAt(i-1). At the same time, traverse the Trie of reversed words from its root. Let the current character betarget.charAt(j)wherejgoes fromi-1down to 0. - If at any point the Trie traversal hits a dead end, we can stop the backward search for the current
i. - If the current Trie node represents a complete (reversed) word, it means
target.substring(j, i)is a word in our dictionary. We can then use this to updatedp[i]:dp[i] = min(dp[i], dp[j] + cost_of_word). - The final answer is
dp[n], or -1 if it's infinity.
Walkthrough
The key optimization is to avoid the linear scan of the words array. A Trie allows us to check for all possible word matches ending at a particular position i much faster.
We build the Trie on reversed words because as we iterate i from 1 to n, for each i, we check suffixes of target.substring(0, i). A suffix like target.substring(j, i) when read backwards (target[i-1], target[i-2], ..., target[j]) can be traced character by character in the Trie of reversed words.
import java.util.Arrays;import java.util.HashMap;import java.util.Map; class TrieNode { TrieNode[] children = new TrieNode[26]; int cost = Integer.MAX_VALUE;} class Solution { public int minimumCost(String target, String[] words, int[] costs) { int n = target.length(); TrieNode root = buildReversedTrie(words, costs); long[] dp = new long[n + 1]; Arrays.fill(dp, Long.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { TrieNode curr = root; for (int j = i - 1; j >= 0; j--) { int charIndex = target.charAt(j) - 'a'; if (curr.children[charIndex] == null) { break; } curr = curr.children[charIndex]; if (curr.cost != Integer.MAX_VALUE && dp[j] != Long.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + curr.cost); } } } return dp[n] == Long.MAX_VALUE ? -1 : (int) dp[n]; } private TrieNode buildReversedTrie(String[] words, int[] costs) { Map<String, Integer> minCosts = new HashMap<>(); for (int i = 0; i < words.length; i++) { minCosts.put(words[i], Math.min(minCosts.getOrDefault(words[i], Integer.MAX_VALUE), costs[i])); } TrieNode root = new TrieNode(); for (Map.Entry<String, Integer> entry : minCosts.entrySet()) { String word = entry.getKey(); int cost = entry.getValue(); TrieNode curr = root; for (int i = word.length() - 1; i >= 0; i--) { int charIndex = word.charAt(i) - 'a'; if (curr.children[charIndex] == null) { curr.children[charIndex] = new TrieNode(); } curr = curr.children[charIndex]; } curr.cost = Math.min(curr.cost, cost); } return root; }}Complexity
Time
O(L + n * k), where `L` is the total length of unique words, `n` is `target.length`, and `k` is the maximum length of a word in `words`. The inner loop runs at most `k` times because any path in the Trie is at most `k` deep.
Space
O(L + n), where `L` is the total length of all unique words (for the Trie) and `n` is for the DP array.
Trade-offs
Pros
Much faster than the naive DP approach.
Efficiently finds all relevant word matches for each DP state.
Cons
The time complexity can still be too high if the maximum word length is large.
The worst-case time complexity is not a significant improvement over the O(n^2) DP if
max_word_lenis close ton.
The most efficient approach treats this as a shortest path problem on an implicit graph and uses the Aho-Corasick algorithm to make it explicit. The indices 0, 1, ..., n of the target string serve as the vertices of our graph. An edge from i to j exists if target.substring(i, j) is one of the words, with the edge weight being its cost. We want the shortest path from vertex 0 to n.
The main challenge is to find all these edges efficiently. The Aho-Corasick algorithm is perfect for this, as it can find all occurrences of multiple patterns (our words) in a text (our target) in time proportional to the text length, pattern lengths, and the number of matches. After building the graph by finding all matches, we can run a shortest path algorithm for DAGs, which is essentially the DP approach but on an explicitly constructed graph.
Algorithm
- Model the problem as finding the shortest path in a graph. The nodes of the graph are the indices of the
targetstring, from 0 ton. - An edge from node
utovexists if the substringtarget.substring(u, v)is present in thewordsarray. The weight of this edge is the cost of that word. - The goal is to find the shortest path from node 0 to node
n. - To find all edges efficiently, we use the Aho-Corasick algorithm. First, build an Aho-Corasick automaton on the given
words. - Traverse the
targetstring with the automaton. At each positioniintarget, the automaton can tell us all words from the dictionary that end exactly ati. For each such wordwof lengthlen, we have found an edge fromi - len + 1toi + 1. - Store these edges in an adjacency list representation of the graph.
- Since the graph is a Directed Acyclic Graph (DAG) (edges only go from smaller indices to larger ones), we can find the shortest path in linear time with respect to the number of vertices and edges.
- Initialize a
dparray (distances) withdp[0] = 0and others to infinity. Iterate fromi = 0ton-1, and for eachi, relax all outgoing edges:dp[v] = min(dp[v], dp[u] + cost). - The final answer is
dp[n].
Walkthrough
This approach is broken down into three main steps:
- Build Aho-Corasick Automaton: Construct the automaton from the unique words and their minimum costs. This includes building the trie, failure links, and dictionary output links to find all matches efficiently. The dictionary links allow us to find all words ending at a position, even if one is a suffix of another (e.g.,
wordscontains "a" and "ba",targetends in "ba"). - Find Matches to Build Graph: Traverse the
targetstring using the automaton. At each positioni, follow the dictionary links from the current state to find all words ending ati. For each match of a wordwwith lengthlenand costc, add a directed edge fromi - len + 1toi + 1with weightcto an adjacency list. - Shortest Path on DAG: With the graph built, compute the shortest path from 0 to
n. Since the vertices0, ..., nare already topologically sorted, a simple DP relaxation works.dp[i]stores the shortest path to vertexi. Iterateufrom 0 ton-1, and for each edge(u, v)with weightc, updatedp[v] = min(dp[v], dp[u] + c).
This method's efficiency comes from the Aho-Corasick algorithm, which avoids re-scanning parts of the target string. The overall complexity is dominated by finding matches and the DAG shortest path calculation.
// The Aho-Corasick implementation is quite lengthy. // Below is a conceptual outline within the main method. import java.util.*; // Assume ACTrieNode and AhoCorasick classes are implemented// ACTrieNode: { children, failureLink, output (list of word lengths and costs) }// AhoCorasick: { build(), getMatches() } class Solution { // Placeholder for a Pair class or use int[] static class Pair { int to; int cost; Pair(int to, int cost) { this.to = to; this.cost = cost; } } public int minimumCost(String target, String[] words, int[] costs) { int n = target.length(); // AhoCorasick ac = new AhoCorasick(words, costs); // List<Match> allMatches = ac.getMatches(target); // Step 1 & 2: Conceptually, build graph using Aho-Corasick // For this example, we'll simulate this by finding edges with a Trie for simplicity, // though AC is more efficient for total match finding. Map<String, Integer> minCosts = new HashMap<>(); for(int i=0; i<words.length; ++i) { minCosts.put(words[i], Math.min(minCosts.getOrDefault(words[i], Integer.MAX_VALUE), costs[i])); } // Build a standard Trie (not reversed) TrieNode root = buildTrie(minCosts); List<Pair>[] adj = new ArrayList[n + 1]; for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>(); for (int i = 0; i < n; i++) { TrieNode curr = root; for (int j = i; j < n; j++) { int charIndex = target.charAt(j) - 'a'; if (curr.children[charIndex] == null) break; curr = curr.children[charIndex]; if (curr.cost != Integer.MAX_VALUE) { adj[i].add(new Pair(j + 1, curr.cost)); } } } // Step 3: Shortest Path on DAG long[] dp = new long[n + 1]; Arrays.fill(dp, Long.MAX_VALUE); dp[0] = 0; for (int i = 0; i <= n; i++) { if (dp[i] == Long.MAX_VALUE) continue; for (Pair edge : adj[i]) { dp[edge.to] = Math.min(dp[edge.to], dp[i] + edge.cost); } } return dp[n] == Long.MAX_VALUE ? -1 : (int) dp[n]; } // Helper to build a standard Trie for the conceptual code private TrieNode buildTrie(Map<String, Integer> minCosts) { TrieNode root = new TrieNode(); for(Map.Entry<String, Integer> entry : minCosts.entrySet()) { String word = entry.getKey(); int cost = entry.getValue(); TrieNode curr = root; for(char c : word.toCharArray()) { int idx = c - 'a'; if(curr.children[idx] == null) curr.children[idx] = new TrieNode(); curr = curr.children[idx]; } curr.cost = cost; } return root; }} // TrieNode used in the conceptual code aboveclass TrieNode { TrieNode[] children = new TrieNode[26]; int cost = Integer.MAX_VALUE;}Complexity
Time
O(L + n + E), where `L` is the total length of unique words, `n` is `target.length`, and `E` is the total number of occurrences of words in `target`. The number of matches `E` can be bounded by `O(n * sqrt(L))`, making this approach efficient enough.
Space
O(L + n + E), where `L` is total length of unique words, `n` is target length, and `E` is the number of matches (edges).
Trade-offs
Pros
The most efficient approach for the given constraints.
Handles the problem in time linear to the input sizes and number of matches.
Cons
More complex to implement due to the Aho-Corasick automaton.
The number of matches (edges) can be large in some cases, though bounded.
Solutions
Solution
class Hashing { private final long [] p ; private final long [] h ; private final long mod ; public Hashing ( String word , long base , int mod ) { int n = word . length (); p = new long [ n + 1 ]; h = new long [ n + 1 ]; p [ 0 ] = 1 ; this . mod = mod ; for ( int i = 1 ; i <= n ; i ++) { p [ i ] = p [ i - 1 ] * base % mod ; h [ i ] = ( h [ i - 1 ] * base + word . charAt ( i - 1 )) % mod ; } } public long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } } class Solution { public int minimumCost ( String target , String [] words , int [] costs ) { final int base = 13331 ; final int mod = 998244353 ; final int inf = Integer . MAX_VALUE / 2 ; int n = target . length (); Hashing hashing = new Hashing ( target , base , mod ); int [] f = new int [ n + 1 ]; Arrays . fill ( f , inf ); f [ 0 ] = 0 ; TreeSet < Integer > ss = new TreeSet <>(); for ( String w : words ) { ss . add ( w . length ()); } Map < Long , Integer > d = new HashMap <>(); for ( int i = 0 ; i < words . length ; i ++) { long x = 0 ; for ( char c : words [ i ]. toCharArray ()) { x = ( x * base + c ) % mod ; } d . merge ( x , costs [ i ], Integer: : min ); } for ( int i = 1 ; i <= n ; i ++) { for ( int j : ss ) { if ( j > i ) { break ; } long x = hashing . query ( i - j + 1 , i ); f [ i ] = Math . min ( f [ i ], f [ i - j ] + d . getOrDefault ( x , inf )); } } return f [ n ] >= inf ? - 1 : f [ n ]; } }class Hashing { private: vector < long > p , h ; long mod ; public: Hashing ( const string & word , long base , long mod ) : p ( word . size () + 1 , 1 ) , h ( word . size () + 1 , 0 ) , mod ( mod ) { for ( int i = 1 ; i <= word . size (); ++ i ) { p [ i ] = p [ i - 1 ] * base % mod ; h [ i ] = ( h [ i - 1 ] * base + word [ i - 1 ]) % mod ; } } long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } }; class Solution { public: int minimumCost ( string target , vector < string >& words , vector < int >& costs ) { const int base = 13331 ; const int mod = 998244353 ; const int inf = INT_MAX / 2 ; int n = target . size (); Hashing hashing ( target , base , mod ); vector < int > f ( n + 1 , inf ); f [ 0 ] = 0 ; set < int > ss ; for ( const string & w : words ) { ss . insert ( w . size ()); } unordered_map < long , int > d ; for ( int i = 0 ; i < words . size (); ++ i ) { long x = 0 ; for ( char c : words [ i ]) { x = ( x * base + c ) % mod ; } d [ x ] = d . find ( x ) == d . end () ? costs [ i ] : min ( d [ x ], costs [ i ]); } for ( int i = 1 ; i <= n ; ++ i ) { for ( int j : ss ) { if ( j > i ) { break ; } long x = hashing . query ( i - j + 1 , i ); if ( d . contains ( x )) { f [ i ] = min ( f [ i ], f [ i - j ] + d [ x ]); } } } return f [ n ] >= inf ? - 1 : f [ n ]; } };class Solution: def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int: base, mod = 13331, 998244353 n = len(target) h = [0] * (n + 1) p = [1] * (n + 1) for i, c in enumerate(target, 1): h[i] = (h[i - 1] * base + ord(c)) % mod p[i] = (p[i - 1] * base) % mod f = [0] + [inf] * n ss = sorted(set(map(len, words))) d = defaultdict(lambda: inf) min = lambda a, b: a if a < b else b for w, c in zip(words, costs): x = 0 for ch in w: x = (x * base + ord(ch)) % mod d[x] = min(d[x], c) for i in range(1, n + 1): for j in ss: if j > i: break x = (h[i] - h[i - j] * p[j]) % mod f[i] = min(f[i], f[i - j] + d[x]) return f[n] if f[n] < inf else - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.