Construct String with Minimum Cost

Construct String with Minimum Cost

What is this problem about?

The Construct String with Minimum Cost interview question provides a target string and a dictionary of words, each with an associated cost. You need to find the minimum total cost to construct the target string by concatenating words from the dictionary. You can use any word multiple times.

Why is this asked in interviews?

This is a HARD difficulty problem often asked by Amazon. It tests the ability to combine Dynamic Programming with high-performance string matching data structures like Tries or Aho-Corasick. The Construct String with Minimum Cost coding problem distinguishes between candidates who know basic DP and those who can optimize the transition step using specialized string structures.

Algorithmic pattern used

This follows the Array, String, Dynamic Programming interview pattern.

• Define dp[i] as the minimum cost to form the prefix of the target string ending at index i.
• To calculate dp[i], look at all words in the dictionary that could end at index i.
• dp[i] = min(dp[i - word.length] + word.cost) for all matching words.
• To avoid O(N * M) complexity where M is dictionary size, use a Trie to search for all suffixes ending at i in a single pass.

Example explanation

Target: "abcdef", Dictionary: {"abc": 10, "def": 5, "abcd": 12, "ef": 2}

1. dp[0] = 0 (empty string).
2. At index 3 ("abc"): dp[3] = dp[0] + 10 = 10.
3. At index 4 ("abcd"): dp[4] = dp[0] + 12 = 12.
4. At index 6 ("abcdef"):
   • Using "def": dp[6] = dp[3] + 5 = 15.
   • Using "ef": dp[6] = dp[4] + 2 = 14. Final min cost: 14.

Common mistakes candidates make

• Naive DP: Using a simple O(N^2) DP without optimizing the string search, leading to TLE (Time Limit Exceeded) on large inputs.
• Incorrect Trie usage: Not storing the minimum cost for a word in the Trie node when multiple identical words have different costs.
• Floating point costs: Handling costs incorrectly if they are non-integers (though usually they are integers).

Interview preparation tip

Master the Aho-Corasick algorithm or Trie-based DP transitions for string optimization problems. These are the gold standard for "multi-pattern matching" tasks.