Construct String with Minimum Cost - Video Solutions

Problem Overview: You are given a target string and a list of words where each word has an associated cost. The goal is to construct the entire target string by concatenating these words so that the total cost is minimized. Each word can be used multiple times, but it must exactly match the portion of the target where it is placed.

Approach 1: Backtracking with Memoization (Exponential → O(n * m * L))

Start from index 0 in the target and recursively try every word that matches the current position. If a word matches, move the pointer forward by its length and add its cost. Without optimization this explores an exponential number of combinations. Memoization stores the minimum cost for each starting index so repeated states are computed once. Time complexity becomes roughly O(n * m * L), where n is the target length, m the number of words, and L the average word length. Space complexity is O(n) for recursion and memo storage.

Approach 2: Dynamic Programming with Word Matching (O(n * m * L))

Define dp[i] as the minimum cost required to construct the prefix target[0..i). Initialize dp[0] = 0. For every position i, iterate through the word list and check whether a word matches the substring starting at i. If it matches, update dp[i + len(word)] = min(dp[i + len(word)], dp[i] + cost). This transforms the search into a forward state transition similar to classic Dynamic Programming. Time complexity is O(n * m * L) due to substring comparisons. Space complexity is O(n).

Approach 3: Top-Down Dynamic Programming with Memoization (O(n * m * L))

This version expresses the same recurrence using recursion. The function dfs(i) returns the minimum cost to build the suffix starting at index i. For every word that matches target[i : i + len(word)], recursively compute dfs(i + len(word)) and add the cost. Memoization avoids recomputing states. The algorithm still performs substring checks, so the complexity remains O(n * m * L) with O(n) space. The approach fits naturally when reasoning about suffix construction and is common in problems combining String processing with Dynamic Programming.

Approach 4: Optimized Matching with Suffix Structures (Up to O(n log n + matches))

When the word list is large, repeated substring comparisons dominate runtime. Preprocessing the target using structures like a Suffix Array, trie, or hashing allows faster substring checks. Instead of scanning every word at every position, you query which words match the current suffix and only transition those states. The DP structure stays the same but matching becomes significantly faster for large datasets.

Recommended for interviews: The bottom-up dynamic programming solution with word matching is usually expected. It clearly shows you understand state transitions and optimal substructure. Mentioning memoized recursion demonstrates the same idea from another direction, while discussing suffix-based optimization shows awareness of scaling constraints for large inputs.