3213. Construct String with Minimum Cost
Problem Description
You are given a string target
that you need to construct, along with an array of strings words
and an array of integers costs
(both arrays have the same length).
Starting with an empty string s
, you can perform the following operation any number of times:
- Select any index
i
from the range[0, words.length - 1]
- Append
words[i]
to the end of strings
- This operation incurs a cost of
costs[i]
Your goal is to find the minimum total cost needed to make string s
equal to the target
string. If it's impossible to construct the target
string using the given words, return -1
.
For example, if target = "abcd"
, words = ["a", "bc", "d", "ab", "cd"]
, and costs = [1, 3, 2, 4, 5]
, you could:
- Append
"ab"
(cost 4) to gets = "ab"
- Append
"cd"
(cost 5) to gets = "abcd"
- Total cost: 4 + 5 = 9
Or alternatively:
- Append
"a"
(cost 1) to gets = "a"
- Append
"bc"
(cost 3) to gets = "abc"
- Append
"d"
(cost 2) to gets = "abcd"
- Total cost: 1 + 3 + 2 = 6
The minimum cost would be 6 in this case.
The key challenge is finding the optimal combination of words that:
- When concatenated in order, form exactly the
target
string - Have the minimum total cost among all valid combinations
Intuition
When we need to build a target string from smaller pieces with minimum cost, this naturally leads us to think about dynamic programming. We can break down the problem into smaller subproblems: what's the minimum cost to build each prefix of the target string?
Let's define f[i]
as the minimum cost to construct the first i
characters of the target. To compute f[i]
, we need to consider all possible ways to reach position i
. We could have arrived at position i
by appending a word that ends exactly at position i
.
For example, if we're trying to build "abcdef" and we're at position 4 (having built "abcd"), we might have gotten there by:
- Building "abc" optimally, then adding "d"
- Building "ab" optimally, then adding "cd"
- Building "a" optimally, then adding "bcd"
- Starting fresh with "abcd"
The key insight is that we need to check if the substring target[i-j:i]
(where j
is the length of a potential word) matches any word in our word list. If it does, we can transition from f[i-j]
to f[i]
with the cost of that word.
However, comparing strings directly for every position would be inefficient. This is where string hashing comes in. By pre-computing hash values for all substrings of the target, we can check if a substring matches a word in O(1)
time instead of O(length)
time.
We also optimize by:
- Pre-computing a hash map that stores the minimum cost for each unique hash value (since multiple words might have the same content but different costs)
- Only considering unique word lengths to avoid redundant checks
- Using rolling hash technique to efficiently compute hash values for all substrings
The state transition becomes: f[i] = min(f[i], f[i-j] + cost_of_matching_word)
for all valid word lengths j
where the substring target[i-j:i]
matches a word in our list.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution implements dynamic programming with string hashing to efficiently find the minimum cost to construct the target string.
String Hashing Setup
First, we compute polynomial rolling hash values for all prefixes of the target string:
h[i]
stores the hash value oftarget[0:i]
p[i]
storesbase^i mod mod
for efficient hash computation- Hash formula:
h[i] = (h[i-1] * base + ord(target[i-1])) % mod
This allows us to compute the hash of any substring target[l:r]
in O(1) time using:
hash(l, r) = (h[r] - h[l] * p[r-l]) % mod
Word Processing
We preprocess the words to create a hash map d
where:
- Key: hash value of a word
- Value: minimum cost among all words with that hash value
This handles cases where multiple words have the same content but different costs - we only keep the cheapest option.
We also extract unique word lengths into ss
(sorted set) to avoid checking impossible lengths.
Dynamic Programming
Initialize f[0] = 0
(no cost for empty string) and f[i] = inf
for all other positions.
For each position i
from 1 to n:
- Enumerate all possible word lengths
j
in ascending order - If
j > i
, break (word too long for current position) - Calculate the hash of substring
target[i-j:i]
using the formula:x = (h[i] - h[i-j] * p[j]) % mod
- If this hash exists in our word dictionary
d
, update:f[i] = min(f[i], f[i-j] + d[x])
This checks if we can reach position i
by:
- First building the string up to position
i-j
with costf[i-j]
- Then appending a word of length
j
that matchestarget[i-j:i]
with costd[x]
Final Result
Return f[n]
if it's less than infinity (meaning the target is constructible), otherwise return -1
.
The time complexity is O(n * m)
where n
is the length of target and m
is the number of unique word lengths. The space complexity is O(n + w)
where w
is the number of words.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Given:
target = "abc"
words = ["a", "bc", "ab", "c"]
costs = [2, 3, 5, 1]
Step 1: String Hashing Setup
First, we compute hash values for all prefixes of "abc" (using base=131, mod=10^9+7):
h[0] = 0
(empty string)h[1] = 97
(hash of "a")h[2] = 97*131 + 98 = 12805
(hash of "ab")h[3] = 12805*131 + 99 = 1677754
(hash of "abc")
We also compute powers: p[0]=1
, p[1]=131
, p[2]=17161
, p[3]=2248091
Step 2: Word Processing
Create hash map d
with minimum costs for each word hash:
- "a" → hash = 97, cost = 2
- "bc" → hash = 98*131 + 99 = 12937, cost = 3
- "ab" → hash = 12805, cost = 5
- "c" → hash = 99, cost = 1
So d = {97: 2, 12937: 3, 12805: 5, 99: 1}
Unique word lengths: ss = {1, 2}
(sorted)
Step 3: Dynamic Programming
Initialize: f[0] = 0
, f[1] = inf
, f[2] = inf
, f[3] = inf
Position i = 1 (building "a"):
- Check length j = 1: substring "a" (positions 0 to 1)
- Hash = h[1] - h[0]*p[1] = 97
- Found in d with cost 2
f[1] = min(inf, f[0] + 2) = 0 + 2 = 2
- Check length j = 2: too long (2 > 1), skip
Position i = 2 (building "ab"):
- Check length j = 1: substring "b" (positions 1 to 2)
- Hash = (h[2] - h[1]p[1]) % mod = (12805 - 97131) % mod = 98
- Not in d, skip
- Check length j = 2: substring "ab" (positions 0 to 2)
- Hash = h[2] - h[0]*p[2] = 12805
- Found in d with cost 5
f[2] = min(inf, f[0] + 5) = 0 + 5 = 5
Position i = 3 (building "abc"):
- Check length j = 1: substring "c" (positions 2 to 3)
- Hash = (h[3] - h[2]p[1]) % mod = (1677754 - 12805131) % mod = 99
- Found in d with cost 1
f[3] = min(inf, f[2] + 1) = 5 + 1 = 6
- Check length j = 2: substring "bc" (positions 1 to 3)
- Hash = (h[3] - h[1]p[2]) % mod = (1677754 - 9717161) % mod = 12937
- Found in d with cost 3
f[3] = min(6, f[1] + 3) = min(6, 2 + 3) = 5
Final Result: f[3] = 5
The minimum cost to build "abc" is 5, achieved by:
- Using "a" (cost 2) to build "a"
- Then using "bc" (cost 3) to complete "abc"
- Total: 2 + 3 = 5
Solution Implementation
1from typing import List
2from collections import defaultdict
3
4class Solution:
5 def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
6 # Rolling hash parameters
7 HASH_BASE = 13331
8 HASH_MOD = 998244353
9
10 target_length = len(target)
11
12 # Precompute rolling hash values for all prefixes of target
13 # hash_values[i] = hash of target[0:i]
14 hash_values = [0] * (target_length + 1)
15 # power_values[i] = HASH_BASE^i mod HASH_MOD
16 power_values = [1] * (target_length + 1)
17
18 # Build rolling hash arrays
19 for i, char in enumerate(target, 1):
20 hash_values[i] = (hash_values[i - 1] * HASH_BASE + ord(char)) % HASH_MOD
21 power_values[i] = (power_values[i - 1] * HASH_BASE) % HASH_MOD
22
23 # dp[i] = minimum cost to construct target[0:i]
24 dp = [0] + [float('inf')] * target_length
25
26 # Get unique word lengths in sorted order for optimization
27 unique_word_lengths = sorted(set(map(len, words)))
28
29 # Map each word's hash to its minimum cost
30 word_hash_to_min_cost = defaultdict(lambda: float('inf'))
31
32 # Calculate hash for each word and store minimum cost
33 for word, cost in zip(words, costs):
34 word_hash = 0
35 for char in word:
36 word_hash = (word_hash * HASH_BASE + ord(char)) % HASH_MOD
37 word_hash_to_min_cost[word_hash] = min(word_hash_to_min_cost[word_hash], cost)
38
39 # Dynamic programming to find minimum cost
40 for i in range(1, target_length + 1):
41 # Try all possible word lengths
42 for word_length in unique_word_lengths:
43 # Skip if word length exceeds current position
44 if word_length > i:
45 break
46
47 # Calculate hash of substring target[i-word_length:i] using rolling hash
48 substring_hash = (hash_values[i] - hash_values[i - word_length] * power_values[word_length]) % HASH_MOD
49
50 # Update dp value if using this word gives a better cost
51 dp[i] = min(dp[i], dp[i - word_length] + word_hash_to_min_cost[substring_hash])
52
53 # Return result: minimum cost if target is constructible, else -1
54 return dp[target_length] if dp[target_length] < float('inf') else -1
55
1class Hashing {
2 private final long[] powerBase; // powerBase[i] = base^i mod modulus
3 private final long[] prefixHash; // prefixHash[i] = hash of string[0...i-1]
4 private final long modulus;
5
6 /**
7 * Constructor for polynomial rolling hash
8 * @param word The string to be hashed
9 * @param base The base for polynomial hashing
10 * @param modulus The modulus for hash calculation
11 */
12 public Hashing(String word, long base, int modulus) {
13 int length = word.length();
14 powerBase = new long[length + 1];
15 prefixHash = new long[length + 1];
16 powerBase[0] = 1;
17 this.modulus = modulus;
18
19 // Precompute powers of base and prefix hashes
20 for (int i = 1; i <= length; i++) {
21 powerBase[i] = powerBase[i - 1] * base % modulus;
22 prefixHash[i] = (prefixHash[i - 1] * base + word.charAt(i - 1)) % modulus;
23 }
24 }
25
26 /**
27 * Query the hash value of substring from index left to right (1-indexed)
28 * @param left Starting index (1-indexed)
29 * @param right Ending index (1-indexed)
30 * @return Hash value of substring
31 */
32 public long query(int left, int right) {
33 // Calculate hash of substring using prefix hash formula
34 return (prefixHash[right] - prefixHash[left - 1] * powerBase[right - left + 1] % modulus + modulus) % modulus;
35 }
36}
37
38class Solution {
39 public int minimumCost(String target, String[] words, int[] costs) {
40 // Constants for polynomial hashing
41 final int BASE = 13331;
42 final int MODULUS = 998244353;
43 final int INFINITY = Integer.MAX_VALUE / 2;
44
45 int targetLength = target.length();
46 Hashing targetHashing = new Hashing(target, BASE, MODULUS);
47
48 // Dynamic programming array: dp[i] = minimum cost to construct target[0...i-1]
49 int[] dp = new int[targetLength + 1];
50 Arrays.fill(dp, INFINITY);
51 dp[0] = 0; // Base case: empty string has cost 0
52
53 // Store unique word lengths for optimization
54 TreeSet<Integer> uniqueWordLengths = new TreeSet<>();
55 for (String word : words) {
56 uniqueWordLengths.add(word.length());
57 }
58
59 // Map from word hash to minimum cost for that word
60 Map<Long, Integer> hashToCost = new HashMap<>();
61 for (int i = 0; i < words.length; i++) {
62 // Calculate hash of current word
63 long wordHash = 0;
64 for (char character : words[i].toCharArray()) {
65 wordHash = (wordHash * BASE + character) % MODULUS;
66 }
67 // Keep minimum cost for words with same hash
68 hashToCost.merge(wordHash, costs[i], Integer::min);
69 }
70
71 // Fill DP table
72 for (int i = 1; i <= targetLength; i++) {
73 // Try all possible word lengths that could end at position i
74 for (int wordLength : uniqueWordLengths) {
75 if (wordLength > i) {
76 break; // Word too long for current position
77 }
78
79 // Get hash of substring that could be matched with a word
80 long substringHash = targetHashing.query(i - wordLength + 1, i);
81
82 // Update minimum cost if this word exists in our dictionary
83 dp[i] = Math.min(dp[i], dp[i - wordLength] + hashToCost.getOrDefault(substringHash, INFINITY));
84 }
85 }
86
87 // Return result: -1 if impossible, otherwise the minimum cost
88 return dp[targetLength] >= INFINITY ? -1 : dp[targetLength];
89 }
90}
91
1class Hashing {
2private:
3 vector<long> power; // power[i] stores base^i mod mod
4 vector<long> hash; // hash[i] stores hash value of prefix [0, i)
5 long mod;
6
7public:
8 // Constructor: precompute powers of base and prefix hashes
9 Hashing(const string& word, long base, long mod)
10 : power(word.size() + 1, 1)
11 , hash(word.size() + 1, 0)
12 , mod(mod) {
13
14 for (int i = 1; i <= word.size(); ++i) {
15 // Precompute base^i mod mod
16 power[i] = power[i - 1] * base % mod;
17 // Compute rolling hash for prefix [0, i)
18 hash[i] = (hash[i - 1] * base + word[i - 1]) % mod;
19 }
20 }
21
22 // Get hash value of substring [l, r] (1-indexed)
23 long query(int l, int r) {
24 // Extract substring hash using prefix hash formula
25 // hash[l, r] = (hash[r] - hash[l-1] * base^(r-l+1)) mod mod
26 return (hash[r] - hash[l - 1] * power[r - l + 1] % mod + mod) % mod;
27 }
28};
29
30class Solution {
31public:
32 int minimumCost(string target, vector<string>& words, vector<int>& costs) {
33 // Constants for polynomial rolling hash
34 const int BASE = 13331;
35 const int MOD = 998244353;
36 const int INF = INT_MAX / 2;
37
38 int n = target.size();
39
40 // Initialize hashing for target string
41 Hashing targetHashing(target, BASE, MOD);
42
43 // dp[i] = minimum cost to construct target[0...i-1]
44 vector<int> dp(n + 1, INF);
45 dp[0] = 0; // Base case: empty string costs 0
46
47 // Store unique word lengths for optimization
48 set<int> wordLengths;
49 for (const string& word : words) {
50 wordLengths.insert(word.size());
51 }
52
53 // Map from word hash to minimum cost of that word
54 unordered_map<long, int> hashToCost;
55 for (int i = 0; i < words.size(); ++i) {
56 // Calculate hash value for current word
57 long wordHash = 0;
58 for (char c : words[i]) {
59 wordHash = (wordHash * BASE + c) % MOD;
60 }
61
62 // Keep minimum cost if word appears multiple times
63 if (hashToCost.find(wordHash) == hashToCost.end()) {
64 hashToCost[wordHash] = costs[i];
65 } else {
66 hashToCost[wordHash] = min(hashToCost[wordHash], costs[i]);
67 }
68 }
69
70 // Dynamic programming to find minimum cost
71 for (int i = 1; i <= n; ++i) {
72 // Try all possible word lengths that could end at position i
73 for (int len : wordLengths) {
74 if (len > i) {
75 break; // Word length exceeds current position
76 }
77
78 // Get hash of substring ending at position i with length len
79 long substringHash = targetHashing.query(i - len + 1, i);
80
81 // If this substring matches a word in dictionary
82 if (hashToCost.contains(substringHash)) {
83 // Update minimum cost
84 dp[i] = min(dp[i], dp[i - len] + hashToCost[substringHash]);
85 }
86 }
87 }
88
89 // Return result: -1 if impossible, otherwise the minimum cost
90 return dp[n] >= INF ? -1 : dp[n];
91 }
92};
93
1// Power array to store base^i mod mod
2let power: number[];
3// Hash array to store hash value of prefix [0, i)
4let hash: number[];
5// Modulo value for hash calculations
6let mod: number;
7
8/**
9 * Initialize hashing arrays and precompute powers and prefix hashes
10 * @param word - The string to compute hashes for
11 * @param base - Base value for polynomial rolling hash
12 * @param modValue - Modulo value to prevent overflow
13 */
14function initializeHashing(word: string, base: number, modValue: number): void {
15 const n = word.length;
16 power = new Array(n + 1).fill(1);
17 hash = new Array(n + 1).fill(0);
18 mod = modValue;
19
20 // Precompute powers of base and rolling hash for each prefix
21 for (let i = 1; i <= n; i++) {
22 // Calculate base^i mod mod
23 power[i] = (power[i - 1] * base) % mod;
24 // Calculate rolling hash for prefix [0, i)
25 hash[i] = (hash[i - 1] * base + word.charCodeAt(i - 1)) % mod;
26 }
27}
28
29/**
30 * Get hash value of substring [left, right] (1-indexed)
31 * @param left - Starting position (1-indexed)
32 * @param right - Ending position (1-indexed)
33 * @returns Hash value of the substring
34 */
35function queryHash(left: number, right: number): number {
36 // Extract substring hash using prefix hash formula
37 // hash[left, right] = (hash[right] - hash[left-1] * base^(right-left+1)) mod mod
38 const substringHash = (hash[right] - (hash[left - 1] * power[right - left + 1]) % mod + mod) % mod;
39 return substringHash;
40}
41
42/**
43 * Find minimum cost to construct target string using given words
44 * @param target - Target string to construct
45 * @param words - Array of available words
46 * @param costs - Cost for each word at corresponding index
47 * @returns Minimum cost to construct target, or -1 if impossible
48 */
49function minimumCost(target: string, words: string[], costs: number[]): number {
50 // Constants for polynomial rolling hash
51 const BASE = 13331;
52 const MOD = 998244353;
53 const INF = Math.floor(Number.MAX_SAFE_INTEGER / 2);
54
55 const n = target.length;
56
57 // Initialize hashing for target string
58 initializeHashing(target, BASE, MOD);
59
60 // dp[i] represents minimum cost to construct target[0...i-1]
61 const dp: number[] = new Array(n + 1).fill(INF);
62 dp[0] = 0; // Base case: empty string has zero cost
63
64 // Collect unique word lengths for optimization
65 const wordLengths = new Set<number>();
66 for (const word of words) {
67 wordLengths.add(word.length);
68 }
69
70 // Map from word hash to minimum cost of that word
71 const hashToCost = new Map<number, number>();
72 for (let i = 0; i < words.length; i++) {
73 // Calculate hash value for current word
74 let wordHash = 0;
75 for (let j = 0; j < words[i].length; j++) {
76 wordHash = (wordHash * BASE + words[i].charCodeAt(j)) % MOD;
77 }
78
79 // Keep minimum cost if word appears multiple times
80 if (!hashToCost.has(wordHash)) {
81 hashToCost.set(wordHash, costs[i]);
82 } else {
83 const currentCost = hashToCost.get(wordHash)!;
84 hashToCost.set(wordHash, Math.min(currentCost, costs[i]));
85 }
86 }
87
88 // Dynamic programming to find minimum cost
89 for (let i = 1; i <= n; i++) {
90 // Try all possible word lengths that could end at position i
91 for (const len of wordLengths) {
92 if (len > i) {
93 continue; // Word length exceeds current position
94 }
95
96 // Get hash of substring ending at position i with length len
97 const substringHash = queryHash(i - len + 1, i);
98
99 // If this substring matches a word in dictionary
100 if (hashToCost.has(substringHash)) {
101 // Update minimum cost
102 const cost = hashToCost.get(substringHash)!;
103 dp[i] = Math.min(dp[i], dp[i - len] + cost);
104 }
105 }
106 }
107
108 // Return result: -1 if impossible, otherwise the minimum cost
109 return dp[n] >= INF ? -1 : dp[n];
110}
111
Time and Space Complexity
Time Complexity: O(n × √L)
The algorithm consists of several parts:
- Computing rolling hash for the target string takes
O(n)
time - Processing all words to build the hash dictionary takes
O(L)
time, whereL
is the sum of lengths of all words - The main dynamic programming loop runs for
n
iterations (from 1 to n) - For each position
i
, we iterate through all unique word lengths inss
- The key insight is that while there could be many words, the number of distinct word lengths is bounded by
O(√L)
. This is because if we havek
distinct lengths, in the worst case they would be 1, 2, 3, ..., k, and their sum would bek(k+1)/2 ≤ L
, which gives usk ≤ √(2L)
, hencek = O(√L)
- For each combination of position and word length, we perform constant time operations (hash calculation and comparison)
Therefore, the total time complexity is O(n) + O(L) + O(n × √L) = O(n × √L)
when n × √L > L
.
Space Complexity: O(n + |d|)
- Arrays
h
,p
, andf
each useO(n+1) = O(n)
space - The sorted set
ss
contains at mostO(√L)
unique lengths - The dictionary
d
stores unique word hashes with their minimum costs, which in the worst case could beO(|words|)
but is bounded by the number of unique words - Since the reference answer states
O(n)
space complexity, this assumes that the dictionary size is dominated byn
or considered separately from the main space analysis
The dominant space usage is O(n)
for the dynamic programming arrays.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Hash Collision Issues
Problem: The rolling hash implementation can produce negative values when computing substring hashes, leading to incorrect hash comparisons and wrong results.
When calculating substring_hash = (hash_values[i] - hash_values[i - word_length] * power_values[word_length]) % HASH_MOD
, the subtraction can produce a negative number before the modulo operation. In Python, this results in a negative hash value, which won't match the positive hash values stored in word_hash_to_min_cost
.
Solution: Ensure the hash value is always positive by adding HASH_MOD when the result is negative:
# Instead of: substring_hash = (hash_values[i] - hash_values[i - word_length] * power_values[word_length]) % HASH_MOD # Use: substring_hash = (hash_values[i] - hash_values[i - word_length] * power_values[word_length] % HASH_MOD + HASH_MOD) % HASH_MOD
2. Integer Overflow in Hash Computation
Problem: When computing hash_values[i - word_length] * power_values[word_length]
, the multiplication can overflow even with modulo operations, potentially causing incorrect results in languages with fixed integer sizes.
Solution: Apply modulo operation to the multiplication before subtraction:
substring_hash = (hash_values[i] - (hash_values[i - word_length] * power_values[word_length]) % HASH_MOD + HASH_MOD) % HASH_MOD
3. Duplicate Words with Different Costs
Problem: While the code handles this correctly by keeping the minimum cost for each hash, developers might forget this edge case and use the first occurrence or last occurrence instead.
Example: If words = ["abc", "abc"]
and costs = [10, 5]
, we must use cost 5, not 10.
Solution: The current implementation correctly uses:
word_hash_to_min_cost[word_hash] = min(word_hash_to_min_cost[word_hash], cost)
4. Empty Words in Input
Problem: If the input contains empty strings in the words
array, they would have a hash of 0 and could incorrectly affect the DP calculation.
Solution: Filter out empty words or add validation:
# Add validation at the beginning
for word, cost in zip(words, costs):
if not word: # Skip empty words
continue
word_hash = 0
for char in word:
word_hash = (word_hash * HASH_BASE + ord(char)) % HASH_MOD
word_hash_to_min_cost[word_hash] = min(word_hash_to_min_cost[word_hash], cost)
5. Hash Function Choice
Problem: Poor choice of hash base and modulo can increase collision probability, leading to incorrect results when different substrings produce the same hash.
Solution: Use well-tested parameters (like base=13331, mod=998244353) or implement double hashing for critical applications:
# Double hashing for better collision resistance HASH_BASE1, HASH_MOD1 = 13331, 998244353 HASH_BASE2, HASH_MOD2 = 10007, 1000000007 # Compute both hashes and use tuple (hash1, hash2) as key
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!