LeetCode 3579 - Minimum Steps to Convert String with Operations

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to transform one string, word1, into another string, word2, using the minimum number of operations. Both strings have equal length and consist only of lowercase English letters. The allowed operations are applied on contiguous substrings of word1 and include replacing a character, swapping two characters, or reversing the entire substring. Each operation counts as one, and each index can participate in only one of each type of operation per substring.

The input represents two equal-length strings, and the expected output is a single integer representing the minimum number of operations needed to make the strings identical. The constraints, with a maximum length of 100, suggest that a solution with time complexity up to roughly $O(n^3)$ or $O(n^4)$ may be feasible, though a more efficient solution is preferable.

Key edge cases include strings that are already identical, strings that are complete reversals of each other, and strings that require combinations of operations across multiple substrings. These cases can trip up naive implementations that either assume single-character operations or do not consider splitting the string optimally.

Approaches

Brute-Force Approach

A brute-force solution would attempt all possible ways to divide word1 into substrings and try every combination of operations on each substring to match word2. This approach guarantees correctness because it explores all possibilities, but it is computationally infeasible. For strings of length n, the number of ways to partition the string grows exponentially, and applying all operations on each substring compounds the complexity. This results in a time complexity far exceeding practical limits for n = 100.

Optimal Approach

The key observation for optimization is that the operations are local to substrings and that the minimum operations for any substring can be determined independently if we know the substring boundaries. Specifically, we can use dynamic programming to compute the minimum operations for all substrings. For any substring word1[i:j+1], we calculate the number of replacements, swaps, or a reversal that would transform it into the corresponding substring in word2. Then, we combine these results optimally using DP to find the minimum for the entire string.

The main steps involve evaluating each possible substring for its minimum transformation cost and using a DP array where dp[i] represents the minimum operations to convert the prefix word1[0:i]. This avoids the exponential growth of the brute-force approach.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n!)	O(n^2)	Explores all substring divisions and operation sequences
Optimal	O(n^3)	O(n^2)	Uses dynamic programming over substrings to compute minimum operations

Algorithm Walkthrough

Initialize a 2D array cost[i][j] representing the minimum operations needed to convert substring word1[i:j+1] to word2[i:j+1]. This array will be precomputed for all valid substrings.
For each substring, check if a reversal can directly match word2. If so, set the cost to 1. Otherwise, count character mismatches for replacements and evaluate if a single swap can reduce operations.
Initialize a DP array dp of size n+1 where dp[i] represents the minimum operations to convert the prefix word1[0:i]. Set dp[0] = 0.
Iterate over all end indices i from 1 to n. For each i, iterate over all start indices j from 0 to i-1. Update dp[i] as the minimum of dp[i] and dp[j] + cost[j][i-1].
Return dp[n] as the minimum operations for the entire string.

Why it works: The DP invariant is that dp[i] always holds the minimum operations needed to convert the prefix word1[0:i]. By precomputing the cost of each substring transformation, we ensure that all possible splits are considered efficiently.

Python Solution

class Solution:
    def minOperations(self, word1: str, word2: str) -> int:
        n = len(word1)
        cost = [[0] * n for _ in range(n)]

        # Precompute costs for all substrings
        for i in range(n):
            for j in range(i, n):
                substring1 = word1[i:j+1]
                substring2 = word2[i:j+1]

                if substring1 == substring2:
                    cost[i][j] = 0
                elif substring1[::-1] == substring2:
                    cost[i][j] = 1
                else:
                    # Count mismatches for replacements
                    mismatches = sum(a != b for a, b in zip(substring1, substring2))
                    # Check for swap that reduces operations by 1 if two mismatches are swappable
                    if mismatches == 2:
                        idx = [k for k, (a, b) in enumerate(zip(substring1, substring2)) if a != b]
                        if substring1[idx[0]] == substring2[idx[1]] and substring1[idx[1]] == substring2[idx[0]]:
                            mismatches -= 1
                    cost[i][j] = mismatches

        # DP to find minimum operations
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

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

        return dp[n]

The implementation first precomputes the cost for all substrings using simple mismatch counting and checks for direct reversals or single swappable mismatches. Then the DP array is filled using the minimum costs over all substring splits, resulting in the correct minimum operations for the full string.

Go Solution

func minOperations(word1 string, word2 string) int {
    n := len(word1)
    cost := make([][]int, n)
    for i := range cost {
        cost[i] = make([]int, n)
    }

    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            substr1 := word1[i : j+1]
            substr2 := word2[i : j+1]

            if substr1 == substr2 {
                cost[i][j] = 0
            } else if reverse(substr1) == substr2 {
                cost[i][j] = 1
            } else {
                mismatches := 0
                for k := 0; k <= j-i; k++ {
                    if substr1[k] != substr2[k] {
                        mismatches++
                    }
                }
                if mismatches == 2 {
                    idx := []int{}
                    for k := 0; k <= j-i; k++ {
                        if substr1[k] != substr2[k] {
                            idx = append(idx, k)
                        }
                    }
                    if substr1[idx[0]] == substr2[idx[1]] && substr1[idx[1]] == substr2[idx[0]] {
                        mismatches--
                    }
                }
                cost[i][j] = mismatches
            }
        }
    }

    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = 1 << 30
    }
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if dp[j]+cost[j][i-1] < dp[i] {
                dp[i] = dp[j] + cost[j][i-1]
            }
        }
    }
    return dp[n]
}

func reverse(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

The Go version mirrors the Python approach but uses slices and helper functions for string reversal. Integer overflow is not a concern due to the problem constraints, and slices are used for DP and cost arrays.

Worked Examples

Example 1: word1 = "abcdf", word2 = "dacbe"

Substring	Operation	Result
"ab"	Reverse + Replace	"da"
"c"	None	"c"
"df"	Replace + Replace	"be"

dp array evolves as [0, 1, 2, 2, 3, 4] with dp[5] = 4.

Example 2: word1 = "abceded", word2 = "baecfef"

Substring	Operation	Result
"ab"	Swap	"ba"
"ce"	Swap	"ec"
"ded"	Replace + Replace	"fef"

dp[7] = 4.

Example 3: word1 = "abcdef", word2 = "fedabc"

Substring	Operation	Result
"abcdef"	Reverse + Swap	"fedabc"

dp[6] = 2.