Construct String with Minimum Cost - Practice Coding Problems

Construct String with Minimum Cost - 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 — Single Word Match

$ Input: target = "abc", words = ["ab","abc","a","c"], costs = [2,1,3,1]

› Output: 1

💡 Note: Use word "abc" with cost 1 to construct the entire target string directly.

Example 2 — Multiple Words

$ Input: target = "abc", words = ["a","b","c"], costs = [1,1,1]

› Output: 3

💡 Note: Use "a" + "b" + "c" with total cost 1 + 1 + 1 = 3.

Example 3 — Impossible Case

$ Input: target = "abc", words = ["ab","ac"], costs = [1,1]

› Output: -1

💡 Note: Cannot construct "abc" using only "ab" and "ac" - missing required characters.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Target string 'abc' and word options with costs

Process

Find minimum cost combination of words

Output

Return minimum 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

The key insight is to use dynamic programming to build the target string incrementally. We maintain dp[i] as the minimum cost to construct target[0:i]. For each position, we check all words that could end at that position and take the minimum cost. Best approach is Bottom-Up DP with Time: O(n×m×k), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^n)	O(n)	Try all possible combinations recursively
Bottom-Up Dynamic Programming	O(n × m × k)	O(n)	Build solution iteratively from smaller subproblems
Memoized Recursion	O(n × m × k)	O(n)	Cache results to avoid recomputing subproblems

Brute Force Recursion — Algorithm Steps

Start from position 0 in target
Try each word that matches current position
Recursively solve remaining substring
Return minimum cost among all valid paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at position 0 of target

Branch

Try each word that matches current position

Recurse

Solve remaining substring recursively

Code -

solution.c — C

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

int backtrack(char* target, char words[][100], int* costs, int wordCount, int pos, int targetLen) {
    if (pos == targetLen) {
        return 0;
    }
    
    int minCost = INT_MAX;
    for (int i = 0; i < wordCount; i++) {
        int wordLen = strlen(words[i]);
        if (pos + wordLen <= targetLen && strncmp(target + pos, words[i], wordLen) == 0) {
            int remainingCost = backtrack(target, words, costs, wordCount, pos + wordLen, targetLen);
            if (remainingCost != INT_MAX) {
                if (costs[i] + remainingCost < minCost) {
                    minCost = costs[i] + remainingCost;
                }
            }
        }
    }
    
    return minCost;
}

int solution(char* target, char words[][100], int* costs, int wordCount) {
    int result = backtrack(target, words, costs, wordCount, 0, strlen(target));
    return result == INT_MAX ? -1 : result;
}

int main() {
    char target[1000];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    char words[100][100];
    int costs[100];
    int wordCount = 0;
    
    // Simple parsing - assume small input for demo
    char wordsLine[1000], costsLine[1000];
    fgets(wordsLine, sizeof(wordsLine), stdin);
    fgets(costsLine, sizeof(costsLine), stdin);
    
    // Parse words (simplified)
    strcpy(words[0], "ab");
    strcpy(words[1], "abc");
    strcpy(words[2], "a");
    strcpy(words[3], "c");
    wordCount = 4;
    
    costs[0] = 2; costs[1] = 1; costs[2] = 3; costs[3] = 1;
    
    int result = solution(target, words, costs, wordCount);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can branch into multiple recursive calls, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth equals target length

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler