MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Minimum Cost to Construct String

Written By ## Minimum Cost to Construct String Introduction

The Minimum Cost to Construct String problem asks us to use the given 2-D array and write a function to calculate the smallest cost to make a string of length n. The key challenge lies in the constraint that no two consecutive positions can have the same character. It's essential to strike a balance between character selection, cost calculation, and meeting the constraints in the problem statement.

## Minimum Cost to Construct String Problem

Use ABCD to construct a string.

Suppose you can only use character A, B, C and D to form a string of length n. You are also given a 2-D integer array of cost[n] meaning for each position (0..n - 1), the cost to use each character (0..3 means A..D). cost[i][j] means the cost to put character j on position i. You cannot have 2 consecutive positions with the same character.

Calculate the smallest cost to make a string of length n.

### Example Inputs and Outputs

#### Example 1

Input: n = 2, cost = [[2, 3, 4, 5], [7, 3, 4, 1]] Output: 3

#### Example 2

Input: n = 4, cost = [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]
Output: 4

## Minimum Cost to Construct String Solutions

To solve this problem, we can use dynamic programming to calculate the smallest cost of constructing a string of length n using characters A, B, C, and D. We start by initializing a 2D array, dp, of size n by 4 to store the cost values. The dp array represents the minimum cost to form a string of length i with character j at position i.

We begin by assigning the cost values for the first row of dp based on the given cost array. Then, we iterate from the second row onwards, calculating the minimum cost for each position i and character j by considering the costs of the previous row and excluding the current character. We update dp[i][j] by adding the cost of character j at position i to the minimum cost from the previous row.

Finally, we find the minimum cost among the values in the last row of dp and return it as the smallest cost to make a string of length n. This approach ensures that we avoid consecutive characters and choose the optimal characters with the lowest cost at each position.

``````def smallestCost(n, cost):
if n <= 0:
return 0

dp = [ * 4 for _ in range(n)]
dp = cost

for i in range(1, n):
for j in range(4):
dp[i][j] = cost[i][j] + min(dp[i-1][k] for k in range(4) if k != j)

return min(dp[n-1])

# Test case
n = 2
cost = [[2, 3, 4, 5], [7, 3, 4, 1]]
print(smallestCost(n, cost))  # Output: 3

n = 4
cost = [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]
print(smallestCost(n, cost))  # Output: 4``````

#### Time/Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the string, as we need to iterate through each position once.
• Space Complexity: O(n), as we use a 2D array of size [n] to store the minimum costs.