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

Number: 3482

Difficulty: Hard

Paid? No

Companies: Mitsogo

Problem Description

Given a target string, a list of words, and a corresponding list of costs, you must determine the minimum cost required to construct the target string by repeatedly appending any of the given words, where each appended word adds its cost. The challenge is to select words (possibly multiple times) in the proper order so that their concatenation exactly equals the target. If the target cannot be successfully constructed, return -1.

Key Insights

  • This is essentially a string segmentation problem with an added twist of minimizing cost.
  • Use dynamic programming to build the solution from left to right.
  • Let dp[i] represent the minimum cost to construct the prefix target[0…i-1].
  • For each position i, only consider words that can match the target substring starting at i.
  • To optimize, preprocess the words by grouping them by their first character so that only candidate words are considered.
  • Finally, traverse the dp array and update future positions if a candidate word fits; the answer will be dp[target.length] if it has been updated.

Space and Time Complexity

Time Complexity: O(n * L) where n is the length of target and L is the average length of candidate words (using candidate grouping can reduce unnecessary comparisons). Space Complexity: O(n) for the dp array and additional space for storing the word groups.

Solution

We use dynamic programming to build the target string one prefix at a time. We initialize a dp array of size (n+1) where dp[0] is 0 (representing an empty string with no cost) and all other entries are set to infinity. For each starting index i in the target (where dp[i] is not infinity), we check the group of words starting with target[i]. For every candidate word, if it matches the target substring starting from i and does not exceed the target length, we update dp[i + len(word)] with the lesser of its current value or dp[i] + cost(word). Finally, if dp[target.length] is still infinity, the target cannot be formed and we return -1; otherwise, that dp value is the answer.

Code Solutions

# Python solution using dynamic programming with candidate grouping

def min_cost_to_construct(target, words, costs):
    n = len(target)
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[0] = 0  # base case: empty string requires zero cost

    # Preprocess words: group candidate words by their first character
    word_dict = {}
    for word, cost in zip(words, costs):
        if word[0] not in word_dict:
            word_dict[word[0]] = []
        word_dict[word[0]].append((word, cost))

    # Dynamic Programming: try to extend prefix at each position i
    for i in range(n):
        if dp[i] == INF:
            continue  # skip unreachable indices
        # If no word starts with target[i], skip candidates.
        if target[i] not in word_dict:
            continue
        # Check all words starting with target[i]
        for candidate, cost in word_dict[target[i]]:
            end = i + len(candidate)
            if end <= n and target[i:end] == candidate:
                dp[end] = min(dp[end], dp[i] + cost)
    
    return dp[n] if dp[n] != INF else -1

# Example usage:
target = "abcdef"
words = ["abdef","abc","d","def","ef"]
costs = [100,1,1,10,5]
print(min_cost_to_construct(target, words, costs))  # Output: 7
← Back to All Questions