#2977

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Cost to Convert String II

Compute the minimum cost to transform source into target using substring replacements with given costs efficiently using dynamic programming.

array string dynamic programming graph trie

Problem Statement

You are given two strings, source and target, of equal length containing lowercase letters. You also have arrays original, changed, and cost representing allowed substring transformations and their respective costs.

You can repeatedly select a substring from source and replace it with a corresponding string in changed at its associated cost, following the rule that any two operations either do not overlap or are applied to the exact same indices. Return the minimum total cost to convert source into target, or -1 if conversion is impossible.

Examples

Example 1

Input: 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]

Output: 28

To convert "abcd" to "acbe", do the following operations:

Change substring source[1..1] from "b" to "c" at a cost of 5.
Change substring source[2..2] from "c" to "e" at a cost of 1.
Change substring source[2..2] from "e" to "b" at a cost of 2.
Change substring source[3..3] from "d" to "e" at a cost of 20. The total cost incurred is 5 + 1 + 2 + 20 = 28. It can be shown that this is the minimum possible cost.

Example 2

Input: source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]

Output: 9

To convert "abcdefgh" to "acdeeghh", do the following operations:

Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation. The total cost incurred is 1 + 3 + 5 = 9. It can be shown that this is the minimum possible cost.

Example 3

Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]

Output: -1

It is impossible to convert "abcdefgh" to "addddddd". If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation. If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.

Constraints

1 <= source.length == target.length <= 1000
source, target consist only of lowercase English characters.
1 <= cost.length == original.length == changed.length <= 100
1 <= original[i].length == changed[i].length <= source.length
original[i], changed[i] consist only of lowercase English characters.
original[i] != changed[i]
1 <= cost[i] <= 106

Solution Approach

Map unique substrings to IDs

Assign a unique integer ID to each substring appearing in original or changed arrays. This allows quick lookup and reduces repeated string comparisons during dynamic programming transitions.

Use state transition dynamic programming

Define dp[i] as the minimum cost to convert the first i characters of source into target. For each substring operation, update dp using dp[start+len] = min(dp[start+len], dp[start] + cost) if it matches the substring and obeys the non-overlapping or identical index rule.

Optimize substring application

Preprocess operations by length and starting index to quickly identify applicable transformations. This reduces redundant checks and ensures the DP transitions only consider valid and cost-effective operations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the number of substring operations and the length of source. Mapping strings to IDs and iterating over operations leads to O(n * m) worst-case, with n = source length and m = number of operations. Space is dominated by dp array and substring mapping.

What Interviewers Usually Probe

Check if candidate correctly handles non-overlapping or identical index rules.
Observe if state transition DP is applied efficiently with substring mapping.
Listen for reasoning about impossible conversions and early pruning strategies.

Common Pitfalls or Variants

Common pitfalls

Forgetting to enforce non-overlapping or identical index constraint between operations.
Failing to efficiently match substrings, leading to TLE on larger inputs.
Ignoring edge cases where conversion is impossible, returning wrong positive cost.

Follow-up variants

Allow wildcard characters in original substrings to match multiple target sequences.
Minimize number of operations instead of total cost while using the same DP framework.
Restrict operations to contiguous blocks of fixed maximum length to test optimized DP transitions.

FAQ

What is the main strategy to solve Minimum Cost to Convert String II?

Use state transition dynamic programming combined with unique substring ID mapping to systematically compute minimum cost.

How do overlapping substrings affect the solution?

Operations must either be on identical indices or completely non-overlapping; violating this rule makes the operation invalid.

Can the algorithm handle large source strings?

Yes, if substring mapping and DP transitions are efficiently implemented, the solution scales up to source length of 1000 and 100 operations.

What should be returned if conversion is impossible?

Return -1 whenever no sequence of allowed substring operations can fully convert source into target.

Does the problem always require using all operations?

No, only operations that contribute to reaching target with minimal cost are applied; unnecessary operations are skipped by DP.

terminal

Solution

Solution 1: Trie + Floyd Algorithm + Memoization Search

According to the problem description, we can consider each string as a node, and the conversion cost between each pair of strings as a directed edge. We first initialize a $26 \times 26$ two-dimensional array $g$, where $g[i][j]$ represents the minimum cost of converting string $i$ to string $j$. Initially, $g[i][j] = \infty$, and if $i = j$, then $g[i][j] = 0$. Here, we can use a trie to store the strings in `original` and `changed` along with their corresponding integer identifiers.

class Node:
    __slots__ = ["children", "v"]

    def __init__(self):
        self.children: List[Node | None] = [None] * 26
        self.v = -1


class Solution:
    def minimumCost(
        self,
        source: str,
        target: str,
        original: List[str],
        changed: List[str],
        cost: List[int],
    ) -> int:
        m = len(cost)
        g = [[inf] * (m << 1) for _ in range(m << 1)]
        for i in range(m << 1):
            g[i][i] = 0
        root = Node()
        idx = 0

        def insert(w: str) -> int:
            node = root
            for c in w:
                i = ord(c) - ord("a")
                if node.children[i] is None:
                    node.children[i] = Node()
                node = node.children[i]
            if node.v < 0:
                nonlocal idx
                node.v = idx
                idx += 1
            return node.v

        @cache
        def dfs(i: int) -> int:
            if i >= len(source):
                return 0
            res = dfs(i + 1) if source[i] == target[i] else inf
            p = q = root
            for j in range(i, len(source)):
                p = p.children[ord(source[j]) - ord("a")]
                q = q.children[ord(target[j]) - ord("a")]
                if p is None or q is None:
                    break
                if p.v < 0 or q.v < 0:
                    continue
                res = min(res, dfs(j + 1) + g[p.v][q.v])
            return res

        for x, y, z in zip(original, changed, cost):
            x = insert(x)
            y = insert(y)
            g[x][y] = min(g[x][y], z)
        for k in range(idx):
            for i in range(idx):
                if g[i][k] >= inf:
                    continue
                for j in range(idx):
                    # g[i][j] = min(g[i][j], g[i][k] + g[k][j])
                    if g[i][k] + g[k][j] < g[i][j]:
                        g[i][j] = g[i][k] + g[k][j]

        ans = dfs(0)
        return -1 if ans >= inf else ans

Continue Practicing

#2976 minimum cost to convert string i #2707 extra characters in a string #3291 minimum number of valid strings to form target i