# Minimum Steps to Convert String with Operations
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-steps-to-convert-string-with-operations)
Canonical: https://scaleengineer.com/dsa/problems/minimum-steps-to-convert-string-with-operations
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
You are given two strings, `word1` and `word2`, of equal length. You need to transform `word1` into `word2`.

For this, divide `word1` into one or more **contiguous substrings**. For each substring `substr` you can perform the following operations:

1. **Replace:** Replace the character at any one index of `substr` with another lowercase English letter.
2. **Swap:** Swap any two characters in `substr`.
3. **Reverse Substring:** Reverse `substr`.

Each of these counts as **one** operation and each character of each substring can be used in each type of operation at most once (i.e. no single index may be involved in more than one replace, one swap, or one reverse).

Return the **minimum number of operations** required to transform `word1` into `word2`.

**Example 1:**

**Input:** word1 = "abcdf", word2 = "dacbe"

**Output:** 4

**Explanation:**

Divide `word1` into `"ab"`, `"c"`, and `"df"`. The operations are:

* For the substring `"ab"`,  
  * Perform operation of type 3 on `"ab" -> "ba"`.
  * Perform operation of type 1 on `"ba" -> "da"`.
* For the substring `"c"` do no operations.
* For the substring `"df"`,  
  * Perform operation of type 1 on `"df" -> "bf"`.
  * Perform operation of type 1 on `"bf" -> "be"`.

**Example 2:**

**Input:** word1 = "abceded", word2 = "baecfef"

**Output:** 4

**Explanation:**

Divide `word1` into `"ab"`, `"ce"`, and `"ded"`. The operations are:

* For the substring `"ab"`,  
  * Perform operation of type 2 on `"ab" -> "ba"`.
* For the substring `"ce"`,  
  * Perform operation of type 2 on `"ce" -> "ec"`.
* For the substring `"ded"`,  
  * Perform operation of type 1 on `"ded" -> "fed"`.
  * Perform operation of type 1 on `"fed" -> "fef"`.

**Example 3:**

**Input:** word1 = "abcdef", word2 = "fedabc"

**Output:** 2

**Explanation:**

Divide `word1` into `"abcdef"`. The operations are:

* For the substring `"abcdef"`,  
  * Perform operation of type 3 on `"abcdef" -> "fedcba"`.
  * Perform operation of type 2 on `"fedcba" -> "fedabc"`.

**Constraints:**

* `1 <= word1.length == word2.length <= 100`
* `word1` and `word2` consist only of lowercase English letters.

# Approaches
## Brute-Force Recursion
This approach uses a straightforward recursive method to explore all possible ways of partitioning `word1`. It breaks down the problem into smaller, identical subproblems. For each possible first substring, it calculates the cost and recursively calls itself for the rest of the string. The minimum of these results is the answer.
**Time:** O(n * 2^n) approximately. The recurrence relation is T(n) = sum_{i=1 to n} (T(n-i) + O(i)), which leads to exponential growth. · **Space:** O(n) for the recursion call stack, where n is the length of the strings.
**Pros:** Simple to understand and implement, as it directly translates the problem definition into code.; Correctly explores all possibilities to find the optimal solution.
**Cons:** Extremely inefficient due to overlapping subproblems. The function `solve(i)` is called multiple times for the same `i`, leading to an exponential number of computations.; Likely to result in a 'Time Limit Exceeded' (TLE) error for larger inputs due to its high time complexity.
### Explanation
The core idea is to define a function `solve(start)` that finds the minimum operations for the suffixes of `word1` and `word2` starting from index `start`. To compute `solve(start)`, we try every possible cut point `end` for the first contiguous substring. This substring `word1[start...end]` is then transformed into `word2[start...end]`. We calculate the cost for this single transformation and add it to the result of the recursive call on the rest of the string, `solve(end + 1)`. The minimum cost over all possible `end` points is the result for `solve(start)`. This method explores the entire search space of partitions, but without memoization, it recomputes solutions for the same subproblems repeatedly.

```java
class Solution {
    public int minimumOperations(String word1, String word2) {
        return solve(0, word1, word2);
    }

    private int solve(int start, String word1, String word2) {
        int n = word1.length();
        if (start == n) {
            return 0;
        }

        int minOps = Integer.MAX_VALUE;
        for (int end = start; end < n; end++) {
            String s1 = word1.substring(start, end + 1);
            String s2 = word2.substring(start, end + 1);
            int cost = calculateCost(s1, s2);
            
            int futureCost = solve(end + 1, word1, word2);
            if (futureCost != Integer.MAX_VALUE) {
                minOps = Math.min(minOps, cost + futureCost);
            }
        }
        return minOps;
    }

    private int calculateCost(String s1, String s2) {
        String reversedS1 = new StringBuilder(s1).reverse().toString();
        int costNoReverse = costHelper(s1, s2);
        int costWithReverse = 1 + costHelper(reversedS1, s2);
        return Math.min(costNoReverse, costWithReverse);
    }

    private int costHelper(String s1, String s2) {
        if (s1.equals(s2)) return 0;

        int[] freq1 = new int[26];
        int[] freq2 = new int[26];
        for (char c : s1.toCharArray()) freq1[c - 'a']++;
        for (char c : s2.toCharArray()) freq2[c - 'a']++;

        int numReplaces = 0;
        boolean isAnagram = true;
        for (int i = 0; i < 26; i++) {
            if (freq1[i] != freq2[i]) isAnagram = false;
            numReplaces += Math.max(0, freq1[i] - freq2[i]);
        }

        if (isAnagram) return 1;

        int[] removals = new int[26];
        int[] additions = new int[26];
        for (int i = 0; i < 26; i++) {
            removals[i] = Math.max(0, freq1[i] - freq2[i]);
            additions[i] = Math.max(0, freq2[i] - freq1[i]);
        }

        int[] s1MisFreq = new int[26];
        int[] s2MisFreq = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                s1MisFreq[s1.charAt(i) - 'a']++;
                s2MisFreq[s2.charAt(i) - 'a']++;
            }
        }

        boolean canFixWithoutSwap = java.util.Arrays.equals(removals, s1MisFreq) && java.util.Arrays.equals(additions, s2MisFreq);

        return canFixWithoutSwap ? numReplaces : numReplaces + 1;
    }
}
```
### Algorithm
1. Define a recursive function, say `solve(start)`, which calculates the minimum operations to convert the suffix `word1[start:]` to `word2[start:]`.
2. The base case for the recursion is when `start` reaches the end of the string (`word1.length()`). In this case, no more characters are left to process, so the cost is 0.
3. In the recursive step, iterate through all possible end points `end` for the first substring, from `start` to `n-1`.
4. For each `end`, the current substring is `word1[start...end]`. Calculate the cost to transform this substring into `word2[start...end]`. Let's call this `cost(start, end)`.
5. The total cost for this choice of substring is `cost(start, end) + solve(end + 1)`.
6. The function `solve(start)` returns the minimum value among all possible choices of `end`.
7. The main challenge is the `cost(start, end)` function. It must calculate the minimum operations for a single substring, considering the `Reverse`, `Swap`, and `Replace` operations. This logic would be the same as in the more efficient dynamic programming approach.
8. The final answer is the result of `solve(0)`.

## Dynamic Programming
This approach improves upon the brute-force recursion by using dynamic programming to store and reuse the results of subproblems. We build a `dp` array where `dp[i]` stores the minimum cost to transform the prefix of length `i`. By iterating through all possible partitions, we can build up the solution from smaller prefixes to the full string.
**Time:** O(n^3). The two nested loops for the DP run in O(n^2). Inside the loops, `calculateCost` is called. This function takes O(L) time where L is the substring length (L <= n). Thus, the total time complexity is O(n^2 * n) = O(n^3). · **Space:** O(n) for the DP array. The space for substrings in each step can be considered, but it doesn't affect the overall asymptotic complexity.
**Pros:** Guaranteed to find the optimal solution.; Significantly more efficient than the brute-force recursive approach.; Handles the problem constraints (n <= 100) effectively.
**Cons:** The time complexity of O(n^3) might be slow for very large constraints, although it's acceptable for n <= 100.; The logic for calculating the cost of a single substring transformation is nuanced and can be tricky to get right.
### Explanation
We use a bottom-up dynamic programming approach. We define an array `dp` of size `n+1`, where `dp[i]` stores the minimum operations needed to convert `word1`'s prefix of length `i` to `word2`'s prefix of length `i`. We initialize `dp[0] = 0` and all other `dp` values to infinity.

We iterate from `i = 1` to `n`. For each `i`, we calculate `dp[i]` by considering all possible previous cut points `j` (from `0` to `i-1`). The last substring in the partition is `word1[j...i-1]`. The cost for this partition is the cost for the prefix `word1[0...j-1]` (which is `dp[j]`) plus the cost to transform the substring `word1[j...i-1]` to `word2[j...i-1]`. We take the minimum over all possible `j`.

The crucial part is calculating the cost for a single substring `s1` to `s2`. This cost is `min(cost_helper(s1, s2), 1 + cost_helper(reverse(s1), s2))`. The `cost_helper` determines the cost using only replacements and swaps. If the character multisets of `s1` and `s2` are different, a certain number of `Replace` operations are mandatory. A single 'Swap' operation is then sufficient to rearrange the resulting anagram into the target string. This 'Swap' operation is only avoided if the `Replace` operations alone can make the strings identical. This happens if the set of characters to be removed/added perfectly matches the characters at mismatched positions.

```java
class Solution {
    public int minimumOperations(String word1, String word2) {
        int n = word1.length();
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // Substring from index j to i-1
                String s1 = word1.substring(j, i);
                String s2 = word2.substring(j, i);
                int cost = calculateCost(s1, s2);
                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + cost);
                }
            }
        }
        return dp[n];
    }

    private int calculateCost(String s1, String s2) {
        String reversedS1 = new StringBuilder(s1).reverse().toString();
        int costNoReverse = costHelper(s1, s2);
        int costWithReverse = 1 + costHelper(reversedS1, s2);
        return Math.min(costNoReverse, costWithReverse);
    }

    private int costHelper(String s1, String s2) {
        if (s1.equals(s2)) {
            return 0;
        }

        int[] freq1 = new int[26];
        int[] freq2 = new int[26];
        for (char c : s1.toCharArray()) {
            freq1[c - 'a']++;
        }
        for (char c : s2.toCharArray()) {
            freq2[c - 'a']++;
        }

        int numReplaces = 0;
        boolean isAnagram = true;
        for (int i = 0; i < 26; i++) {
            if (freq1[i] != freq2[i]) {
                isAnagram = false;
            }
            numReplaces += Math.max(0, freq1[i] - freq2[i]);
        }

        if (isAnagram) {
            return 1; // s1 != s2, but anagrams, so 1 swap op
        }

        // Not anagrams, need replacements
        int[] removals = new int[26];
        int[] additions = new int[26];
        for (int i = 0; i < 26; i++) {
            removals[i] = Math.max(0, freq1[i] - freq2[i]);
            additions[i] = Math.max(0, freq2[i] - freq1[i]);
        }

        int[] s1MisFreq = new int[26];
        int[] s2MisFreq = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                s1MisFreq[s1.charAt(i) - 'a']++;
                s2MisFreq[s2.charAt(i) - 'a']++;
            }
        }

        boolean canFixWithoutSwap = java.util.Arrays.equals(removals, s1MisFreq) && java.util.Arrays.equals(additions, s2MisFreq);

        return canFixWithoutSwap ? numReplaces : numReplaces + 1;
    }
}
```
### Algorithm
1. This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming.
2. Let `dp[i]` be the minimum number of operations to convert the prefix `word1[0...i-1]` into `word2[0...i-1]`.
3. The base case is `dp[0] = 0`, as converting an empty string requires no operations.
4. To compute `dp[i]`, we consider all possible last substrings. The last substring can be `word1[j...i-1]` for any `0 <= j < i`.
5. The transition formula is: `dp[i] = min(dp[j] + cost(j, i-1))` for all `0 <= j < i`, where `cost(j, i-1)` is the minimum cost to transform `word1[j...i-1]` to `word2[j...i-1]`.
6. The `cost` for a single substring `s1` to `s2` is calculated by considering two main options:
    a. Without reversing `s1`: `cost_helper(s1, s2)`.
    b. With reversing `s1`: `1 + cost_helper(reverse(s1), s2)`.
    The final cost is the minimum of these two options.
7. The `cost_helper(s1, s2)` function calculates the cost using only `Replace` and `Swap` operations. 
    a. If `s1` and `s2` are anagrams, the cost is 0 if they are identical, and 1 (for a single conceptual 'Swap' operation to rearrange all characters) if they are not.
    b. If they are not anagrams, we need `numReplaces` operations to match their character multisets. An additional 'Swap' operation (cost 1) is needed unless the replacements can be perfectly aligned with the character mismatches to make the strings identical without any further rearrangement.
8. The final answer is `dp[n]`.