LeetCode 3213 - Construct String with Minimum Cost

The problem asks us to construct a target string target by repeatedly appending strings from a given array words, where each word has an associated cost in costs. The goal is to determine the minimum total cost to construct target exactly.

leetcodehardarraystringdynamic-programmingsuffix-array

LeetCode Problem 3213

Difficulty: 🔴 Hard
Topics: Array, String, Dynamic Programming, Suffix Array

Solution

Problem Understanding

The problem asks us to construct a target string target by repeatedly appending strings from a given array words, where each word has an associated cost in costs. The goal is to determine the minimum total cost to construct target exactly. If it is impossible to form target from the given words, the function should return -1.

The input consists of:

  • target: a string of length up to 50,000 characters.
  • words: an array of strings, each of which can be appended to s.
  • costs: an array of integers representing the cost to append the corresponding word in words.

The constraints tell us several important points:

  1. The sum of all word lengths in words is limited to 50,000, meaning the total input size is manageable.
  2. Each cost is positive, so there are no free operations.
  3. All strings contain only lowercase letters, so we can safely compare substrings without extra preprocessing.

Important edge cases include:

  • Words that cannot match any prefix of target, leading to an impossible construction (-1 output).
  • Multiple ways to construct target with different combinations of words and costs, requiring a dynamic programming solution to choose the minimum.
  • target being very short or words being longer than target, which should be handled correctly.

Approaches

Brute Force Approach

A brute-force solution would try all sequences of words to see if they form target, summing the costs and keeping track of the minimum. For each position in target, we would recursively attempt to append every word that matches the current suffix. While correct, this approach is exponentially slow (O(words.length ^ target.length)) and infeasible for large inputs because the number of combinations grows rapidly.

Optimal Approach

The key observation is that this problem is a dynamic programming problem. We can define dp[i] as the minimum cost to form the prefix target[0:i]. For each position i, we check all words w that can end at i (i.e., target[i-len(w):i] == w). If a word matches, we update dp[i] as the minimum of dp[i] and dp[i-len(w)] + cost_of_w.

This approach works efficiently because each word is only considered where it can potentially match, and each prefix of target is computed exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(words.length ^ target.length) O(target.length) Exponentially many sequences to check, impractical
Optimal DP O(target.length * average_word_count_matching) O(target.length) DP builds minimum cost prefix by prefix using word matches

Algorithm Walkthrough

  1. Initialize a DP array dp of size len(target) + 1 with inf to represent unreachable states. Set dp[0] = 0 because forming an empty string costs nothing.
  2. Iterate over i from 1 to len(target). For each i, check every word in words:
  • Let w_len be the length of the word.
  • If i >= w_len and the substring target[i-w_len:i] equals the word, update dp[i] as the minimum of its current value and dp[i-w_len] + cost.
  1. After filling the DP array, check dp[len(target)]. If it is still inf, return -1, meaning target is impossible to form. Otherwise, return dp[len(target)].

Why it works: The invariant is that dp[i] always represents the minimum cost to form the prefix target[0:i]. By considering all possible words ending at each position, we ensure that we explore all valid sequences without redundant computations.

Python Solution

from typing import List

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        n = len(target)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        word_map = {}
        for w, c in zip(words, costs):
            if w in word_map:
                word_map[w] = min(word_map[w], c)
            else:
                word_map[w] = c
        
        for i in range(1, n + 1):
            for w, cost in word_map.items():
                w_len = len(w)
                if i >= w_len and target[i-w_len:i] == w:
                    dp[i] = min(dp[i], dp[i-w_len] + cost)
        
        return dp[n] if dp[n] != float('inf') else -1

The implementation first maps each word to its minimum cost to avoid redundant comparisons for duplicate words. The DP array iteratively computes the minimum cost to form each prefix of target. At each step, only words that can match the current suffix are considered, keeping the computation efficient.

Go Solution

func minimumCost(target string, words []string, costs []int) int {
    n := len(target)
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = 1<<60 // represent infinity
    }
    dp[0] = 0

    wordMap := make(map[string]int)
    for i, w := range words {
        if val, ok := wordMap[w]; ok {
            if costs[i] < val {
                wordMap[w] = costs[i]
            }
        } else {
            wordMap[w] = costs[i]
        }
    }

    for i := 1; i <= n; i++ {
        for w, cost := range wordMap {
            wLen := len(w)
            if i >= wLen && target[i-wLen:i] == w {
                if dp[i-wLen]+cost < dp[i] {
                    dp[i] = dp[i-wLen] + cost
                }
            }
        }
    }

    if dp[n] >= 1<<60 {
        return -1
    }
    return dp[n]
}

Go differences include using 1<<60 as infinity and handling maps explicitly for minimum costs. The substring comparison works similarly to Python slices.

Worked Examples

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

i dp[i] Explanation
0 0 empty string
1 inf no matching words
2 inf no matching words
3 1 "abc" matches target[0:3], cost 1
4 2 "d" matches target[3:4], dp[3]+1=2
5 inf no matching word
6 7 "ef" matches target[4:6], dp[4]+5=7

Answer: 7.

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

No words match any prefix, so dp[4] = inf, answer -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m) n = len(target), m = number of unique words. Each prefix checks all words
Space O(n + m) DP array of size n+1 and map of unique words

The time complexity is acceptable because the sum of word lengths is bounded and we only consider valid word matches for each position.

Test Cases

# Provided examples
assert Solution().minimumCost("abcdef", ["abdef","abc","d","def","ef"], [100,1,1,10,5]) == 7  # standard case
assert Solution().minimumCost("aaaa", ["z","zz","zzz"], [1,10,100]) == -1  # impossible case

# Edge cases
assert Solution().minimumCost("", [], []) == 0  # empty target
assert Solution().minimumCost("a", ["a"], [1]) == 1  # single character match
assert Solution().minimumCost("abc", ["a","b","c","ab","bc"], [1,1,1,2,2]) == 3  # multiple combinations
assert Solution().minimumCost("aaaaa", ["aa","aaa"], [1,2]) == 3  # choose minimal combination of words
assert Solution().minimumCost("xyz", ["x","y","z"], [10,20,30]) == 60  # all single letters
Test Why
"abcdef" case Verifies minimal cost selection over multiple options
"aaaa" case Verifies handling impossible targets
empty target Edge case of zero-length string
single character match Simple base case
multiple combinations Verifies DP selects optimal combination
repeated minimal words Ensures DP aggregates multiple occurrences correctly
all single letters Confirms cost aggregation across many small words

Edge Cases

  1. Empty Target: If target is an empty string, the minimum cost should always be 0 since no operations are needed. The DP array initialization handles this naturally with `dp