Construct String with Minimum Cost (Easy)

Construct String with Minimum Cost (Easy) - Problem

You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.

Imagine an empty string s.

You can perform the following operation any number of times (including zero):

Choose an index i in the range [0, words.length - 1].
Append words[i] to s.
The cost of operation is costs[i].

Return the minimum cost to make s equal to target. If it's not possible, return -1.

Input & Output

Example 1 — Basic Case

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

› Output: 7

💡 Note: The minimum cost is achieved by: "abc" (cost 1) + "d" (cost 1) + "ef" (cost 5) = 7

Example 2 — Impossible Case

$ Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

› Output: -1

💡 Note: It's impossible to construct "aaaa" using words that only contain 'z'

Example 3 — Single Word Match

$ Input: target = "abc", words = ["abc"], costs = [5]

› Output: 5

💡 Note: Use the single word "abc" with cost 5 to match the entire target

Constraints

1 ≤ target.length ≤ 5 × 10⁴
1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 5 × 10⁴
1 ≤ costs[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Target string "abcdef" and available words with costs

Process

Find optimal combination of words to build target

Output

Return minimum total cost or -1 if impossible

Key Takeaway

🎯 Key Insight: Use dynamic programming to find the minimum cost combination of words that can construct the target string

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 28

This problem requires finding the minimum cost to construct a target string by concatenating words. The key insight is using dynamic programming where dp[i] represents the minimum cost to build target[0:i]. For each position, we try all words that can extend from that position. Time: O(n × m × k), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ 1D Dynamic Programming	O(n × m × k)	O(n)	Build solutions bottom-up using 1D DP array
Recursive with Memoization	O(n × m × k)	O(n)	Try all possible word combinations recursively

1D Dynamic Programming — Algorithm Steps

Initialize DP array with infinity, dp[0] = 0
For each position i, try all words that can end at position i
Update dp[i] with minimum cost
Return dp[n] or -1 if impossible

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0] = 0, all others = infinity

Forward Pass

For each position, try extending with each word

Update

Update dp[i + wordLen] with minimum cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_TARGET_LEN 1000
#define MAX_WORDS 100
#define MAX_WORD_LEN 100

int solution(char* target, char words[][MAX_WORD_LEN], int* costs, int numWords) {
    int n = strlen(target);
    int* dp = (int*)malloc((n + 1) * sizeof(int));
    
    for (int i = 0; i <= n; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    for (int i = 0; i <= n; i++) {
        if (dp[i] == INT_MAX) continue;
        for (int j = 0; j < numWords; j++) {
            int wordLen = strlen(words[j]);
            if (i + wordLen <= n && strncmp(target + i, words[j], wordLen) == 0) {
                if (dp[i] + costs[j] < dp[i + wordLen]) {
                    dp[i + wordLen] = dp[i] + costs[j];
                }
            }
        }
    }
    
    int result = dp[n] == INT_MAX ? -1 : dp[n];
    free(dp);
    return result;
}

int main() {
    char target[MAX_TARGET_LEN];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    char wordsLine[2000];
    fgets(wordsLine, sizeof(wordsLine), stdin);
    
    char costsLine[1000];
    fgets(costsLine, sizeof(costsLine), stdin);
    
    // Parse words
    char words[MAX_WORDS][MAX_WORD_LEN];
    int numWords = 0;
    char* token = strtok(wordsLine, "[\"]");
    while (token != NULL && numWords < MAX_WORDS) {
        if (strlen(token) > 1 && token[0] != ',' && token[0] != ']') {
            strcpy(words[numWords], token);
            numWords++;
        }
        token = strtok(NULL, "[\"]");
    }
    
    // Parse costs
    int costs[MAX_WORDS];
    int numCosts = 0;
    char* costToken = strtok(costsLine, "[,]");
    while (costToken != NULL && numCosts < MAX_WORDS) {
        costs[numCosts] = atoi(costToken);
        numCosts++;
        costToken = strtok(NULL, "[,]");
    }
    
    int result = solution(target, words, costs, numWords);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

n is target length, m is number of words, k is average word length for substring operations

✓ Linear Growth

Space Complexity

O(n)

DP array of size n to store minimum costs for each position

⚡ Linearithmic Space

34.6K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

1D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler