# Construct String with Minimum Cost
**Difficulty:** HARD
[External](https://leetcode.com/problems/construct-string-with-minimum-cost)
Canonical: https://scaleengineer.com/dsa/problems/construct-string-with-minimum-cost
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, String, Suffix Array
**Companies:** [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## 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 `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 <= 5 * 104`
* `1 <= words.length == costs.length <= 5 * 104`
* `1 <= words[i].length <= target.length`
* The total sum of `words[i].length` is less than or equal to `5 * 104`.
* `target` and `words[i]` consist only of lowercase English letters.
* `1 <= costs[i] <= 104`

# Approaches
## Naive Dynamic Programming
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.
**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.
**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 `words` array.; Substring operations inside loops are costly.; Will time out for the given constraints.
### Explanation
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.

```java
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.
### Algorithm
1. Define a DP array `dp` of size `n+1`, where `n` is the length of `target`. `dp[i]` will store the minimum cost to construct the prefix `target.substring(0, i)`.
2. Initialize `dp[0] = 0` (cost to build an empty string is zero) and all other `dp[i]` to infinity.
3. Iterate through each possible end position `i` of a prefix, from 1 to `n`.
4. For each `i`, iterate through each possible start position `j` from 0 to `i-1`.
5. Extract the substring `sub = target.substring(j, i)`.
6. Iterate through the entire `words` array. If `sub` matches a `words[k]`, it represents a valid move.
7. If a match is found, update `dp[i]` with the minimum cost: `dp[i] = min(dp[i], dp[j] + costs[k])`.
8. After filling the `dp` array, `dp[n]` contains the minimum cost for the entire `target` string. If `dp[n]` is still infinity, it's impossible to form the target, so return -1.

## Dynamic Programming with Trie
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]`.
**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.
**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_len` is close to `n`.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Pre-process the `words` and `costs` to 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.
2. Define a DP array `dp` of size `n+1`, where `dp[i]` stores the minimum cost to build `target.substring(0, i)`.
3. Initialize `dp[0] = 0` and all other `dp[i]` to infinity.
4. Iterate `i` from 1 to `n`. To compute `dp[i]`, we look for words in our dictionary that are suffixes of `target.substring(0, i)`.
5. For each `i`, traverse backwards from `target.charAt(i-1)`. At the same time, traverse the Trie of reversed words from its root. Let the current character be `target.charAt(j)` where `j` goes from `i-1` down to 0.
6. If at any point the Trie traversal hits a dead end, we can stop the backward search for the current `i`.
7. 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 update `dp[i]`: `dp[i] = min(dp[i], dp[j] + cost_of_word)`.
8. The final answer is `dp[n]`, or -1 if it's infinity.

## Aho-Corasick with Shortest Path on DAG
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.
**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).
**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.
### Explanation
This approach is broken down into three main steps:
1.  **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., `words` contains "a" and "ba", `target` ends in "ba").
2.  **Find Matches to Build Graph**: Traverse the `target` string using the automaton. At each position `i`, follow the dictionary links from the current state to find all words ending at `i`. For each match of a word `w` with length `len` and cost `c`, add a directed edge from `i - len + 1` to `i + 1` with weight `c` to an adjacency list.
3.  **Shortest Path on DAG**: With the graph built, compute the shortest path from 0 to `n`. Since the vertices `0, ..., n` are already topologically sorted, a simple DP relaxation works. `dp[i]` stores the shortest path to vertex `i`. Iterate `u` from 0 to `n-1`, and for each edge `(u, v)` with weight `c`, update `dp[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.

```java
// 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 above
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    int cost = Integer.MAX_VALUE;
}

```
### Algorithm
1. Model the problem as finding the shortest path in a graph. The nodes of the graph are the indices of the `target` string, from 0 to `n`.
2. An edge from node `u` to `v` exists if the substring `target.substring(u, v)` is present in the `words` array. The weight of this edge is the cost of that word.
3. The goal is to find the shortest path from node 0 to node `n`.
4. To find all edges efficiently, we use the Aho-Corasick algorithm. First, build an Aho-Corasick automaton on the given `words`.
5. Traverse the `target` string with the automaton. At each position `i` in `target`, the automaton can tell us all words from the dictionary that end exactly at `i`. For each such word `w` of length `len`, we have found an edge from `i - len + 1` to `i + 1`.
6. Store these edges in an adjacency list representation of the graph.
7. 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.
8. Initialize a `dp` array (distances) with `dp[0] = 0` and others to infinity. Iterate from `i = 0` to `n-1`, and for each `i`, relax all outgoing edges: `dp[v] = min(dp[v], dp[u] + cost)`.
9. The final answer is `dp[n]`.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

```cpp
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 ]; } };
```

### Python

```python
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 - 1

```