How to Solve Construct String with Minimum Cost

Start by recognizing that each position in the target string can be approached as a state in dynamic programming. For every prefix of the target, track the minimal cost to reach it by adding compatible words. Efficient string matching with hashing or Aho-Corasick automaton ensures transitions are correctly calculated without redundant checks.

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

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.

How GhostInterview Helps

• Identifies correct state transition formulation and tracks minimal costs automatically.
• Highlights efficient matching strategies to prevent timeouts on large inputs.
• Explains common DP pitfalls specifically tied to constructing strings with cost constraints.

Topic Pages

• Array
• String
• Dynamic Programming
• Suffix Array

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.