#3213

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Construct String with Minimum Cost

This problem asks you to construct a target string using given words at minimal cost using dynamic programming techniques efficiently.

array string dynamic programming suffix array

Problem Statement

You are given a target string, an array of words, and a corresponding array of costs. Starting with an empty string, your goal is to build the target string by concatenating words from the array. Each word addition incurs a cost from the costs array, and you can reuse words multiple times if needed.

Determine the minimal total cost to construct the target string. If it is impossible to form the target string using the given words, return -1. Operations should consider exact matches and order to ensure correctness under large input constraints.

Examples

Example 1

Input: target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

Output: 7

The minimum cost can be achieved by performing the following operations:

Example 2

Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

Output: -1

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

Solution Approach

Dynamic Programming State Definition

Define dp[i] as the minimum cost to build the prefix target[0..i-1]. Initialize dp[0] = 0 and other positions as infinity. For each index, attempt to extend the prefix with every word that matches the current position.

Efficient Matching of Words

Use hashing or an Aho-Corasick automaton to quickly find which words can match the target at each position. This avoids repeated substring checks and ensures that the state transitions remain fast even with large word arrays.

State Transition and Cost Update

For every match at position i, update dp[i + len(word)] = min(dp[i + len(word)], dp[i] + cost). Iterate through the target string sequentially to propagate minimal costs. The final answer is dp[target.length] if reachable, otherwise -1.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N * M) in the worst case where N is target length and M is total sum of words length, optimized by efficient word matching. Space complexity is O(N) for the DP array plus additional structures for string matching.

What Interviewers Usually Probe

Check for overlapping word matches that could reduce total cost.
Notice when certain prefixes cannot be completed, signaling a -1 result.
Expect usage of hashing or trie-based structures to manage many word transitions.

Common Pitfalls or Variants

Common pitfalls

Failing to reuse words correctly leading to higher cost than necessary.
Ignoring the order of words causing invalid string construction.
Inefficient substring matching causing TLE on large input sizes.

Follow-up variants

Change costs array to allow negative values and require handling minimal net cost.
Restrict each word to be used at most once and compute the minimal cost.
Find all possible minimal cost sequences instead of just the total minimal cost.

FAQ

What is the main pattern used in Construct String with Minimum Cost?

This problem uses state transition dynamic programming where each prefix of the target string represents a DP state.

Can words be reused multiple times?

Yes, you can reuse words any number of times to construct the target string at minimal cost.

What should be returned if the target string cannot be formed?

Return -1 when it is impossible to construct the target string using the given words.

Which string matching methods help optimize this problem?

Using hashing or an Aho-Corasick automaton efficiently identifies which words match at each target position.

What are common mistakes in implementing the solution?

Ignoring order of words, failing to reuse words optimally, or using naive substring matching causing timeouts are typical errors.

terminal

Solution

Solution 1: String Hashing + Dynamic Programming + Enumerating Length

We define $f[i]$ as the minimum cost to construct the first $i$ characters of $\textit{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 $\textit{target}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

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

Continue Practicing

#3291 minimum number of valid strings to form target i #3292 minimum number of valid strings to form target ii #3316 find maximum removals from source string