We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct String with Minimum Cost (Easy)

Number: 3480

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a target string, an array of words, and an array of costs (each corresponding to a word), you need to construct the target string by repeatedly appending one of the words to an initially empty string. Each operation of appending a chosen word incurs a specified cost. The goal is to determine the minimum total cost needed to construct the target string. If it is impossible to construct the target, return -1.

Key Insights

  • Use dynamic programming to track the minimum cost of constructing every prefix of the target.
  • Let dp[i] denote the minimum cost to form the prefix target[0:i].
  • For each position in the target, iterate through every word and check if it fits exactly starting from that position.
  • If the word fits, update the dp for the end index of that word using the cost of the current operation.
  • The final answer will be stored in dp[target.length]. If no sequence of words can form the target, return -1.

Space and Time Complexity

Time Complexity: O(n * m * k) where n is the length of target, m is the number of words, and k is the average length of word (for substring comparison) Space Complexity: O(n) for the dp array

Solution

We solve the problem with a dynamic programming (DP) approach:

  1. We initialize a DP array (dp) where dp[i] represents the minimum cost to form the prefix target[0:i]. Start with dp[0] = 0.
  2. For every position i in the target string, iterate through each word in words.
  3. Check if the word can be placed starting at index i without exceeding the target length, and if the corresponding substring of target equals the given word.
  4. If a match is found, update dp[i + len(word)] to be the minimum of its current value and dp[i] + cost corresponding to that word.
  5. Finally, dp[target.length] contains the answer if it is not infinity. Otherwise, return -1 if the target cannot be formed.

The key trick is to reduce the problem to constructing prefixes and use a DP recurrence to capture the minimal cost at each step.

Code Solutions

# Python solution with detailed comments
def minCost(target, words, costs):
    n = len(target)
    # Initialize dp array with infinity and set dp[0] = 0
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    
    # Iterate over each position in the target string
    for i in range(n):
        # If current position is unreachable, skip it
        if dp[i] == float('inf'):
            continue
        # Try each word from the words list
        for word, cost in zip(words, costs):
            end = i + len(word)
            # Check if word can fit from position i and matches target substring
            if end <= n and target[i:end] == word:
                dp[end] = min(dp[end], dp[i] + cost)
    
    # If target cannot be formed, return -1
    return dp[n] if dp[n] != float('inf') else -1

# Example usage:
print(minCost("abcdef", ["abdef","abc","d","def","ef"], [100,1,1,10,5]))  # Output: 7
print(minCost("aaaa", ["z","zz","zzz"], [1,10,100]))                       # Output: -1
← Back to All Questions