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 II

Number: 3238

Difficulty: Hard

Paid? No

Companies: Atlassian

Problem Description

Given two strings, source and target, of equal length, and a set of allowed operations—each operation allowing you to replace a substring exactly equal to some string (from the list “original”) by another string (from the list “changed”) at a fixed cost—find the minimum cost to convert source into target. When performing operations, any two chosen substring operations must either be completely disjoint (their index ranges do not overlap) or exactly identical (covering the same indices). You may apply any number of operations. Return the minimum cost if conversion is possible; otherwise, return -1.

Key Insights

  • The allowed operations only work on substrings whose length matches that of one of the provided “original” strings.
  • Operations on disjoint segments effectively partition the conversion into independent subproblems.
  • Operations on the same segment may be chained – conceptually forming a graph where each vertex is a string (of fixed length) and an edge represents an allowed conversion with its cost.
  • For segments where the source already equals the target substring, no cost is needed.
  • By grouping operations by their lengths (since an operation only applies to substrings of a fixed length), we can precompute the minimum cost (using, for example, Floyd–Warshall or Dijkstra) to convert any string into any other string among the “nodes” in that group.
  • Finally, use dynamic programming over the positions of the overall string: dp[i] represents the minimum cost to convert the prefix source[0..i-1] into target[0..i-1]. For every position i and every allowed segment length L (or even when no operation is available, if source[i:i+L] already equals target[i:i+L]) update dp[i+L].

Space and Time Complexity

Time Complexity: O(n * m + Σ_L (N_L^3))
• (n = length of source, m = number of distinct allowed operation lengths, N_L = number of distinct strings in the graph of operations of length L)
Space Complexity: O(n + Σ_L N_L^2)
• dp array size O(n); additional space is used to store the transformation graphs for each substring length.

Solution

We solve the problem in two main parts:

  1. Preprocessing per Operation Length:

    • Group the allowed operations by their string lengths.
    • For each length L, build a graph. Each node is a string that appears as an “original” (and possibly as a “changed”) value in an operation of length L.
    • Add a directed edge from node u to node v with weight cost if there is a direct allowed operation that converts u to v.
    • Using either Floyd–Warshall or running Dijkstra from every vertex, precompute the minimum cost to transform any string u (of length L) into any string v (of length L). This gives a “conversion cost” lookup table for that length.

  2. Dynamic Programming over the main string:

    • Let dp[i] be the minimum cost to convert source[0..i-1] into target[0..i-1]. Initialize dp[0] = 0.
    • For each position i, consider every allowed segment length L (such that i+L <= n). Let Sseg = source[i:i+L] and Tseg = target[i:i+L].
    • If Sseg equals Tseg, then dp[i+L] can be updated with dp[i] (zero extra cost).
    • Otherwise, if there is a conversion possibility (i.e. Sseg and Tseg are in the graph for length L and a finite conversion cost is computed), update dp[i+L] with dp[i] plus the conversion cost.
    • The answer is dp[n] if it is finite; otherwise, the conversion is impossible and return -1.

Key gotcha: Only substrings with lengths that appear in at least one allowed operation can be “converted” (if they are not already equal) because allowed operations apply only for those lengths.

Code Solutions

# Python solution with detailed comments

from collections import defaultdict, deque
import math

def minCostToConvert(source, target, original, changed, cost):
    n = len(source)
    dp = [math.inf] * (n + 1)
    dp[0] = 0
    
    # Group operations by the length of the substring they apply to.
    ops_by_length = defaultdict(list)
    for orig, chng, c in zip(original, changed, cost):
        L = len(orig)
        ops_by_length[L].append((orig, chng, c))
    
    # Precompute the minimum conversion cost for each substring length.
    # For each length L, only strings that appear in any operation are considered.
    convCost = {}  # Key: L, Value: dict of dict, i.e., convCost[L][u][v] = min cost to convert string u -> v.
    
    for L, ops in ops_by_length.items():
        nodes = set()
        for orig_str, chng_str, _ in ops:
            nodes.add(orig_str)
            nodes.add(chng_str)
        nodes = list(nodes)
        # Initialize distance: for the same node, cost 0
        dist = {u: {v: math.inf for v in nodes} for u in nodes}
        for u in nodes:
            dist[u][u] = 0
        
        # Add direct edges per given operation (sometimes there are multiple operations for the same conversion; take the minimum cost)
        for orig_str, chng_str, c in ops:
            if c < dist[orig_str][chng_str]:
                dist[orig_str][chng_str] = c
        
        # Floyd-Warshall to compute all pairs shortest conversion cost for this substring length.
        for k in nodes:
            for i in nodes:
                for j in nodes:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        convCost[L] = dist  # Save the computed distances for length L.
    
    # Dynamic Programming over positions in the source string.
    for i in range(n):
        if dp[i] == math.inf:
            continue  # Skip if current prefix cannot be converted.
        # Consider each allowed length L that we have operations for.
        for L in ops_by_length.keys():
            if i + L > n: 
                continue
            Sseg = source[i:i+L]
            Tseg = target[i:i+L]
            # Option 1: if the substring already equals target, no cost needed.
            if Sseg == Tseg:
                dp[i+L] = min(dp[i+L], dp[i])
            
            # Option 2: If the segment does not match, attempt conversion.
            # The allowed operations only work if Sseg and Tseg appear among our nodes.
            if Sseg in convCost[L] and Tseg in convCost[L][Sseg]:
                conversion_cost = convCost[L][Sseg][Tseg]
                if conversion_cost < math.inf:
                    dp[i+L] = min(dp[i+L], dp[i] + conversion_cost)
    
    return dp[n] if dp[n] < math.inf else -1

# Example usage:
if __name__ == "__main__":
    source = "abcd"
    target = "acbe"
    original = ["a","b","c","c","e","d"]
    changed = ["b","c","b","e","b","e"]
    cost = [2,5,5,1,2,20]
    print(minCostToConvert(source, target, original, changed, cost))
    # Expected output: 28
← Back to All Questions