This problem requires calculating the minimum total cost to convert one string into another using substring replacement operations. Each operation has a specific cost and must follow the non-overlapping or identical index rule. Using state transition dynamic programming allows systematic exploration of all valid operation sequences while minimizing the total cost.
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.
How GhostInterview Helps
- Automatically maps substrings to IDs and manages dynamic programming states efficiently.
- Identifies minimum cost sequences and flags impossible conversions with precise index validation.
- Provides step-by-step application of each operation, highlighting cost accumulation and rule enforcement.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Minimum Cost to Convert String II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Minimum Cost to Convert String II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
This problem asks to calculate the minimum cost to convert a string from source to target using specific character transformation operations.
Open problem page#2707 Extra Characters in a StringThe problem asks for the minimum number of extra characters left after optimally breaking a string into substrings found in a dictionary.
Open problem page#3291 Minimum Number of Valid Strings to Form Target IUse dynamic programming to split target into the fewest prefixes that match any word prefix, while ruling out dead positions early.
Open problem page