Minimum Steps to Convert String with Operations

Hard

#3187Time: 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.

Patterns

Dynamic Programming Greedy

Data structures

String

Prompt

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:

Replace: Replace the character at any one index of substr with another lowercase English letter.
Swap: Swap any two characters in substr.
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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Define a recursive function, say solve(start), which calculates the minimum operations to convert the suffix word1[start:] to word2[start:].
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.
In the recursive step, iterate through all possible end points end for the first substring, from start to n-1.
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).
The total cost for this choice of substring is cost(start, end) + solve(end + 1).
The function solve(start) returns the minimum value among all possible choices of end.
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.
The final answer is the result of solve(0).

Walkthrough

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.

1class Solution {2    public int minimumOperations(String word1, String word2) {3        return solve(0, word1, word2);4    }5 6    private int solve(int start, String word1, String word2) {7        int n = word1.length();8        if (start == n) {9            return 0;10        }11 12        int minOps = Integer.MAX_VALUE;13        for (int end = start; end < n; end++) {14            String s1 = word1.substring(start, end + 1);15            String s2 = word2.substring(start, end + 1);16            int cost = calculateCost(s1, s2);17            18            int futureCost = solve(end + 1, word1, word2);19            if (futureCost != Integer.MAX_VALUE) {20                minOps = Math.min(minOps, cost + futureCost);21            }22        }23        return minOps;24    }25 26    private int calculateCost(String s1, String s2) {27        String reversedS1 = new StringBuilder(s1).reverse().toString();28        int costNoReverse = costHelper(s1, s2);29        int costWithReverse = 1 + costHelper(reversedS1, s2);30        return Math.min(costNoReverse, costWithReverse);31    }32 33    private int costHelper(String s1, String s2) {34        if (s1.equals(s2)) return 0;35 36        int[] freq1 = new int[26];37        int[] freq2 = new int[26];38        for (char c : s1.toCharArray()) freq1[c - 'a']++;39        for (char c : s2.toCharArray()) freq2[c - 'a']++;40 41        int numReplaces = 0;42        boolean isAnagram = true;43        for (int i = 0; i < 26; i++) {44            if (freq1[i] != freq2[i]) isAnagram = false;45            numReplaces += Math.max(0, freq1[i] - freq2[i]);46        }47 48        if (isAnagram) return 1;49 50        int[] removals = new int[26];51        int[] additions = new int[26];52        for (int i = 0; i < 26; i++) {53            removals[i] = Math.max(0, freq1[i] - freq2[i]);54            additions[i] = Math.max(0, freq2[i] - freq1[i]);55        }56 57        int[] s1MisFreq = new int[26];58        int[] s2MisFreq = new int[26];59        for (int i = 0; i < s1.length(); i++) {60            if (s1.charAt(i) != s2.charAt(i)) {61                s1MisFreq[s1.charAt(i) - 'a']++;62                s2MisFreq[s2.charAt(i) - 'a']++;63            }64        }65 66        boolean canFixWithoutSwap = java.util.Arrays.equals(removals, s1MisFreq) && java.util.Arrays.equals(additions, s2MisFreq);67 68        return canFixWithoutSwap ? numReplaces : numReplaces + 1;69    }70}

Complexity

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.

Trade-offs

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.

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.

Algorithm

This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming.
Let dp[i] be the minimum number of operations to convert the prefix word1[0...i-1] into word2[0...i-1].
The base case is dp[0] = 0, as converting an empty string requires no operations.
To compute dp[i], we consider all possible last substrings. The last substring can be word1[j...i-1] for any 0 <= j < i.
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].
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.
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.
The final answer is dp[n].

Walkthrough

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.

1class Solution {2    public int minimumOperations(String word1, String word2) {3        int n = word1.length();4        int[] dp = new int[n + 1];5        java.util.Arrays.fill(dp, Integer.MAX_VALUE);6        dp[0] = 0;7 8        for (int i = 1; i <= n; i++) {9            for (int j = 0; j < i; j++) {10                // Substring from index j to i-111                String s1 = word1.substring(j, i);12                String s2 = word2.substring(j, i);13                int cost = calculateCost(s1, s2);14                if (dp[j] != Integer.MAX_VALUE) {15                    dp[i] = Math.min(dp[i], dp[j] + cost);16                }17            }18        }19        return dp[n];20    }21 22    private int calculateCost(String s1, String s2) {23        String reversedS1 = new StringBuilder(s1).reverse().toString();24        int costNoReverse = costHelper(s1, s2);25        int costWithReverse = 1 + costHelper(reversedS1, s2);26        return Math.min(costNoReverse, costWithReverse);27    }28 29    private int costHelper(String s1, String s2) {30        if (s1.equals(s2)) {31            return 0;32        }33 34        int[] freq1 = new int[26];35        int[] freq2 = new int[26];36        for (char c : s1.toCharArray()) {37            freq1[c - 'a']++;38        }39        for (char c : s2.toCharArray()) {40            freq2[c - 'a']++;41        }42 43        int numReplaces = 0;44        boolean isAnagram = true;45        for (int i = 0; i < 26; i++) {46            if (freq1[i] != freq2[i]) {47                isAnagram = false;48            }49            numReplaces += Math.max(0, freq1[i] - freq2[i]);50        }51 52        if (isAnagram) {53            return 1; // s1 != s2, but anagrams, so 1 swap op54        }55 56        // Not anagrams, need replacements57        int[] removals = new int[26];58        int[] additions = new int[26];59        for (int i = 0; i < 26; i++) {60            removals[i] = Math.max(0, freq1[i] - freq2[i]);61            additions[i] = Math.max(0, freq2[i] - freq1[i]);62        }63 64        int[] s1MisFreq = new int[26];65        int[] s2MisFreq = new int[26];66        for (int i = 0; i < s1.length(); i++) {67            if (s1.charAt(i) != s2.charAt(i)) {68                s1MisFreq[s1.charAt(i) - 'a']++;69                s2MisFreq[s2.charAt(i) - 'a']++;70            }71        }72 73        boolean canFixWithoutSwap = java.util.Arrays.equals(removals, s1MisFreq) && java.util.Arrays.equals(additions, s2MisFreq);74 75        return canFixWithoutSwap ? numReplaces : numReplaces + 1;76    }77}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem