We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Convert String I

Number: 3235

Difficulty: Medium

Paid? No

Companies: Google, Atlassian

Problem Description

Given two strings, source and target, of equal length and consisting of lowercase letters, you are allowed to perform a series of transformations. For each allowed transformation provided as parallel arrays (original, changed) with associated cost values, you can change a character from the string if there exists a corresponding transformation (or chain of transformations) that takes you from one letter to another. The goal is to determine the minimum total cost required to convert source into target, applying any number of these operations. If it is impossible to convert the string, return -1.

Key Insights

  • Model the allowed transformations as a directed weighted graph where nodes represent letters.
  • For each allowed transformation, update the edge with the minimum cost if multiple operations exist for the same pair.
  • Use the Floyd Warshall algorithm to compute the minimum conversion cost between every pair of letters.
  • For each position in the source string, if the minimal cost to convert the source letter to the target letter is not available (infinite), the conversion is impossible.
  • Sum up the conversion cost for each character position, applying the transformation cost computed via the graph.

Space and Time Complexity

Time Complexity: O(26^3 + n), where n is the length of the strings. The 26^3 part comes from the Floyd Warshall algorithm on 26 English letters. Space Complexity: O(26^2) for the cost matrix, plus O(n) for input strings.

Solution

The problem can be solved by first modeling the transformations as a graph where each node is a letter ('a'-'z'). Every allowed operation creates a directed edge from letter x to letter y with a weight equal to the operation's cost. If there are multiple operations between the same pair, we take the one with the smallest cost.

After constructing the graph, we apply the Floyd Warshall algorithm to compute the minimum cost path between every pair of letters. This gives us the cheapest way to transform any letter into any other letter (possibly via intermediate transformations).

Finally, we iterate over each index of the source string. For each character, if the source and target letters are the same, no cost is incurred. Otherwise, we add the minimum cost to transform the source letter to the target letter based on our computed graph. If any transformation is impossible (i.e., remains infinite), we return -1.

Code Solutions

# Python solution with line-by-line comments
def minimumCost(source, target, original, changed, cost):
    # There are 26 letters, so we use an indexed list to represent the transformation costs
    INF = float('inf')
    n_letters = 26
    # Initialize the cost matrix with INF and 0 cost for same letter transformations
    dist = [[INF] * n_letters for _ in range(n_letters)]
    for i in range(n_letters):
        dist[i][i] = 0
    
    # Update the cost matrix with the provided operations
    for op_orig, op_changed, op_cost in zip(original, changed, cost):
        i = ord(op_orig) - ord('a')
        j = ord(op_changed) - ord('a')
        # Ensure we store the minimum cost if multiple operations exist
        dist[i][j] = min(dist[i][j], op_cost)
    
    # Apply Floyd Warshall to compute minimum cost for all pairs of letters
    for k in range(n_letters):
        for i in range(n_letters):
            for j in range(n_letters):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # Calculate the total conversion cost from source to target
    total_cost = 0
    for s_char, t_char in zip(source, target):
        # If the characters are the same, no cost is needed
        if s_char == t_char:
            continue
        i = ord(s_char) - ord('a')
        j = ord(t_char) - ord('a')
        # If the conversion is impossible, return -1
        if dist[i][j] == INF:
            return -1
        total_cost += dist[i][j]
    return total_cost

# Example usage:
print(minimumCost("abcd", "acbe", ["a","b","c","c","e","d"], ["b","c","b","e","b","e"], [2,5,5,1,2,20]))
print(minimumCost("aaaa", "bbbb", ["a","c"], ["c","b"], [1,2]))
print(minimumCost("abcd", "abce", ["a"], ["e"], [10000]))
← Back to All Questions