3213. Construct String with Minimum Cost

HardArrayStringDynamic ProgrammingSuffix Array

Problem Description

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

Consider an initially empty string s. You can perform the following operation any number of times:

Choose an index i from the range [0, words.length - 1].
Append words[i] to s.
The cost associated with this operation is costs[i].

The task is to find the minimum cost required to make the string s equal to the target string. If it is not possible to form the target, return -1.

Intuition

The solution involves two main techniques: string hashing and dynamic programming. The core idea is to efficiently check if certain segments of the target string can be formed using the given words while tracking the cost involved. To do this:

Dynamic Programming Setup: Define an array f where f[i] represents the minimum cost to construct the substring of target of length i. Initialize f[0] to 0, representing no cost for the empty string, and other entries to infinity, as we initially assume no solution for them.
String Hashing: Use string hashing to efficiently compare substring segments. Calculate hash values for the target and the words. By precomputing the power of the base (used in hashing), it becomes efficient to calculate and compare substring hashes.
Transition Logic: For each position i in the target, check all possible word lengths j. If a word of this length can form a valid substring ending at i, calculate the hash for the substring and compare it with the hash of any of the words. If a match is found, update the cost f[i] using the value at f[i-j] plus the cost of the current word.

This approach ensures that all potential constructions of the target are evaluated while minimizing cost, leading to an efficient solution to the problem.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a combination of string hashing, dynamic programming, and enumerating lengths to efficiently form the target string with the minimum cost. Here's a step-by-step breakdown of the approach:

Initialize Variables:
- Use a base (base = 13331) and a modulus (mod = 998244353) for hashing purposes.
- Compute hash values (h) and powers (p) for each prefix of the target string. These are used to quickly obtain hash values of any substring.
Dynamic Programming Array:
- Create a dynamic programming array f, initialized such that f[0] = 0 (cost for an empty prefix is zero) and all other positions are set to infinity.
Compute Minimum Costs per Hash:
- Use a dictionary d to map each word's hash to its minimum cost, ensuring that if multiple words hash to the same value, the cheapest one is used.
Iterate Over the Target:
- For every position i in the target, enumerate potential lengths j that can be formed from the previously established words.
- Compute the hash for the substring ending at i and having length j.
- Update the minimum cost f[i] using the hash value to check against stored minimum costs in the dictionary d.
Return the Result:
- If the entire target can be formed (f[n] is not infinity), return f[n]. Otherwise, return -1 to indicate it's not possible to form target with the given words and costs.

The algorithm efficiently balances between trying multiple combinations of words while keeping track of costs using hashing and dynamic programming. This approach ensures that substring matches are performed in near constant time, leveraging the power of hash comparisons.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's work through a small example to illustrate the solution approach.

Suppose we have the target string catdog, an array of words as ["cat", "dog", "cow"], and their corresponding costs as [5, 7, 10].

Initialization:
- Base for hashing: base = 13331
- Modulus for hashing: mod = 998244353
- Initialize the dynamic programming array f with f[0] = 0 and all others to infinity, as no cost is assigned yet: f = [0, ∞, ∞, ∞, ∞, ∞, ∞].
Compute Hashes:
- Calculate hashes for all prefixes of target: h("c"), h("ca"), h("cat"), and so forth.
- Calculate powers of base to be used in hash computations.
Map Word Hashes to Costs:
- Compute hash for each word:
  - Hash h("cat"), map it to cost 5.
  - Hash h("dog"), map it to cost 7.
  - Hash h("cow"), map it to cost 10.
Dynamic Programming Over Target:
- Iterate over the target string:
  - At i = 3 (substring cat), the hash matches h("cat"), so update f[3] with f[0] + 5: f = [0, ∞, ∞, 5, ∞, ∞, ∞].
  - At i = 6 (entire target catdog), the substring dog hash matches h("dog"), update f[6] with f[3] + 7: f = [0, ∞, ∞, 5, ∞, ∞, 12].
Final Result:
- Since f[6] is 12 and not infinity, it's possible to construct target catdog with a minimum cost of 12.

Through this example, the solution approach demonstrates integrating hashing with dynamic programming to find the optimal way to construct the target with minimum cost.

Solution Implementation

1from collections import defaultdict
2from typing import List
3from math import inf
4
5class Solution:
6    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
7        # Define the base and modulus for hashing
8        base, mod = 13331, 998244353
9        n = len(target)
10
11        # Precompute hash values and powers of the base for the target string
12        h = [0] * (n + 1)
13        p = [1] * (n + 1)
14        for i, c in enumerate(target, 1):
15            h[i] = (h[i - 1] * base + ord(c)) % mod
16            p[i] = (p[i - 1] * base) % mod
17
18        # Initialize the cost array with infinity
19        f = [0] + [inf] * n
20
21        # Create a sorted set of word lengths
22        word_lengths = sorted(set(map(len, words)))
23
24        # Dictionary to store the minimum cost for each word based on its hash
25        word_cost_map = defaultdict(lambda: inf)
26
27        # Custom minimum function to retain minimum values
28        min_cost = lambda a, b: a if a < b else b
29
30        # Compute hash for each word and store the minimum cost in the dictionary
31        for word, cost in zip(words, costs):
32            word_hash = 0
33            for char in word:
34                word_hash = (word_hash * base + ord(char)) % mod
35            word_cost_map[word_hash] = min_cost(word_cost_map[word_hash], cost)
36
37        # Dynamic programming approach to find the minimum cost to form the target
38        for i in range(1, n + 1):
39            for length in word_lengths:
40                if length > i:
41                    break
42                # Calculate hash for the substring of target ending at position i and of length 'length'
43                current_hash = (h[i] - h[i - length] * p[length]) % mod
44                # Update the cost for forming the target up to index i
45                f[i] = min_cost(f[i], f[i - length] + word_cost_map[current_hash])
46
47        # Return the minimum cost to form the entire target, or -1 if not possible
48        return f[n] if f[n] < inf else -1
49

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4import java.util.TreeSet;
5
6class Hashing {
7    private final long[] prefixPowers; // Prefix powers of the base
8    private final long[] hashValues;   // Hash values for prefixes of the string
9    private final long mod;
10
11    // Constructor to initialize hash and power arrays
12    public Hashing(String word, long base, int mod) {
13        int n = word.length();
14        prefixPowers = new long[n + 1];
15        hashValues = new long[n + 1];
16        prefixPowers[0] = 1;
17        this.mod = mod;
18      
19        // Precompute powers and hash values
20        for (int i = 1; i <= n; i++) {
21            prefixPowers[i] = prefixPowers[i - 1] * base % mod;
22            hashValues[i] = (hashValues[i - 1] * base + word.charAt(i - 1)) % mod;
23        }
24    }
25
26    // Compute hash value of substring from index l to r (1-based)
27    public long query(int l, int r) {
28        return (hashValues[r] - hashValues[l - 1] * prefixPowers[r - l + 1] % mod + mod) % mod;
29    }
30}
31
32class Solution {
33    // Main function to compute minimum cost to form the target string using available words and their costs
34    public int minimumCost(String target, String[] words, int[] costs) {
35        final int base = 13331;
36        final int mod = 998244353;
37        final int inf = Integer.MAX_VALUE / 2;
38
39        int n = target.length();
40        Hashing hashing = new Hashing(target, base, mod);
41
42        // Initialize the cost array with infinite values
43        int[] minCost = new int[n + 1];
44        Arrays.fill(minCost, inf);
45        minCost[0] = 0;
46
47        // Collect lengths of all words in a TreeSet for quick access
48        TreeSet<Integer> wordLengths = new TreeSet<>();
49        for (String word : words) {
50            wordLengths.add(word.length());
51        }
52
53        // Map to store the minimum cost of words with a given hash
54        Map<Long, Integer> hashToCostMap = new HashMap<>();
55        for (int i = 0; i < words.length; i++) {
56            long hashValue = 0;
57            for (char c : words[i].toCharArray()) {
58                hashValue = (hashValue * base + c) % mod;
59            }
60            hashToCostMap.merge(hashValue, costs[i], Integer::min);
61        }
62
63        // Dynamic programming to compute minimum cost
64        for (int i = 1; i <= n; i++) {
65            for (int wordLength : wordLengths) {
66                if (wordLength > i) {
67                    break;
68                }
69                long substringHash = hashing.query(i - wordLength + 1, i);
70                minCost[i] = Math.min(minCost[i], minCost[i - wordLength] + hashToCostMap.getOrDefault(substringHash, inf));
71            }
72        }
73
74        // Return the minimum cost if achievable, otherwise -1
75        return minCost[n] >= inf ? -1 : minCost[n];
76    }
77}
78

1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <set>
5#include <climits>
6#include <string>
7using namespace std;
8
9// Class for Hashing using polynomial rolling hash
10class Hashing {
11private:
12    vector<long> basePowers; // To store powers of the base
13    vector<long> hashValues; // To store hash values of prefixes
14    long modValue; // Modulo value for hashing
15
16public:
17    // Constructor for precomputing powers and hash values
18    Hashing(const string& word, long base, long mod)
19        : basePowers(word.size() + 1, 1)
20        , hashValues(word.size() + 1, 0)
21        , modValue(mod) {
22        for (int i = 1; i <= word.size(); ++i) {
23            basePowers[i] = basePowers[i - 1] * base % mod;
24            hashValues[i] = (hashValues[i - 1] * base + word[i - 1]) % mod;
25        }
26    }
27
28    // Function to get hash value of a substring from l to r
29    long query(int l, int r) {
30        return (hashValues[r] - hashValues[l - 1] * basePowers[r - l + 1] % modValue + modValue) % modValue;
31    }
32};
33
34// Class representing the solution for the problem
35class Solution {
36public:
37    // Method to find the minimum cost to construct the target string
38    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
39        const int base = 13331; // Base value for hashing
40        const int mod = 998244353; // Modulo value for hashing
41        const int infiniteCost = INT_MAX / 2; // Represents a high cost value
42
43        int n = target.size();
44        Hashing hashing(target, base, mod);
45
46        vector<int> minCost(n + 1, infiniteCost);
47        minCost[0] = 0;
48
49        set<int> wordLengths;
50        for (const string& word : words) {
51            wordLengths.insert(word.size());
52        }
53
54        unordered_map<long, int> wordCostMap;
55        for (int i = 0; i < words.size(); ++i) {
56            long hashValue = 0;
57            for (char c : words[i]) {
58                hashValue = (hashValue * base + c) % mod;
59            }
60            wordCostMap[hashValue] = wordCostMap.find(hashValue) == wordCostMap.end() ? costs[i] : min(wordCostMap[hashValue], costs[i]);
61        }
62
63        for (int i = 1; i <= n; ++i) {
64            for (int length : wordLengths) {
65                if (length > i) {
66                    break; // If the length of the word is more than current position, break
67                }
68                long currentHash = hashing.query(i - length + 1, i);
69                if (wordCostMap.contains(currentHash)) {
70                    minCost[i] = min(minCost[i], minCost[i - length] + wordCostMap[currentHash]);
71                }
72            }
73        }
74
75        return minCost[n] >= infiniteCost ? -1 : minCost[n]; // If the cost is still infinite, return -1
76    }
77};
78

1// Base and modulo values for hashing
2const base: number = 13331;
3const mod: number = 998244353;
4// A high cost value, set to half of the maximum integer value
5const infiniteCost: number = Math.floor(Number.MAX_SAFE_INTEGER / 2);
6
7// Precomputes powers of the base and hash values of prefixes for a word
8function precomputeHashes(word: string): { basePowers: number[], hashValues: number[] } {
9    const n = word.length;
10    const basePowers: number[] = new Array(n + 1).fill(1);
11    const hashValues: number[] = new Array(n + 1).fill(0);
12
13    for (let i = 1; i <= n; ++i) {
14        basePowers[i] = basePowers[i - 1] * base % mod;
15        hashValues[i] = (hashValues[i - 1] * base + word.charCodeAt(i - 1)) % mod;
16    }
17
18    return { basePowers, hashValues };
19}
20
21// Gets the hash value of a substring from l to r using precomputed hash values
22function queryHash(l: number, r: number, basePowers: number[], hashValues: number[]): number {
23    return (hashValues[r] - hashValues[l - 1] * basePowers[r - l + 1] % mod + mod) % mod;
24}
25
26// Minimum cost to construct the target string using given words and their associated costs
27function minimumCost(target: string, words: string[], costs: number[]): number {
28    const { basePowers, hashValues } = precomputeHashes(target);
29    const n: number = target.length;
30
31    const minCost: number[] = new Array(n + 1).fill(infiniteCost);
32    minCost[0] = 0;
33
34    // Obtain unique word lengths in a set
35    const wordLengths: Set<number> = new Set<number>();
36    words.forEach(word => wordLengths.add(word.length));
37
38    // Create a map of hash values of words to their minimum costs
39    const wordCostMap: Map<number, number> = new Map<number, number>();
40    words.forEach((word, index) => {
41        let hashValue: number = 0;
42        for (let i = 0; i < word.length; i++) {
43            hashValue = (hashValue * base + word.charCodeAt(i)) % mod;
44        }
45        const currentCost = wordCostMap.get(hashValue);
46        wordCostMap.set(hashValue, currentCost === undefined ? costs[index] : Math.min(currentCost, costs[index]));
47    });
48
49    // Determine the minimum cost to reach each position in the target string
50    for (let i = 1; i <= n; i++) {
51        for (const length of wordLengths) {
52            if (length > i) {
53                break; // Skip words longer than the current index
54            }
55            const currentHash = queryHash(i - length + 1, i, basePowers, hashValues);
56            const wordCost = wordCostMap.get(currentHash);
57            if (wordCost !== undefined) {
58                minCost[i] = Math.min(minCost[i], minCost[i - length] + wordCost);
59            }
60        }
61    }
62
63    // Return -1 if the cost is still infinite, otherwise return the computed minimum cost
64    return minCost[n] >= infiniteCost ? -1 : minCost[n];
65}
66

Time and Space Complexity

The time complexity of the code is O(n \times \sqrt{L}). This complexity arises from the combination of iterating over the target string target and checking substrings of varying lengths determined by the length of all words. Within the longest loop for each character in target, the program searches within the set of lengths of words, which potentially scales to \sqrt{L} due to the nature of the operations performed, including substring hash calculations.

The space complexity is O(n). This is because additional data structures store information regarding the target string, such as hashed values and polynomial terms (h and p arrays), both of which only increase linearly with the input size n.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know