Skip to main content
Talentd

Minimum Steps to Convert String with Operations - Solution & Explanation

HardStringDynamic Programming14 min read
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a string and a set of allowed operations that modify characters or segments. The goal is to transform the string into the required form using the minimum number of operations. Each decision can affect future transformations, which makes this a classic optimization problem over strings.

Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)

The naive strategy explores every possible sequence of operations. At each index you decide whether to apply an operation or move to the next character. This creates a recursion tree where many states repeat because the same substring configurations appear multiple times. The approach works for very small inputs but becomes infeasible quickly due to exponential growth. Its main value is conceptual: it reveals the overlapping subproblems that motivate a dynamic programming solution.

Approach 2: Greedy + Dynamic Programming (O(n^2) time, O(n) space)

The optimal solution tracks the minimum cost required to process prefixes of the string. Define dp[i] as the minimum operations needed to correctly convert the first i characters. For each position, evaluate valid operations that could end at that index and update the state using previous results. Greedy observations help prune transitions—for example, when consecutive characters can be handled by a single operation or when extending an earlier transformation costs less than starting a new one.

While iterating through the string, the algorithm checks earlier breakpoints and updates the DP state with the cheapest achievable transformation. Each state reuses results from smaller prefixes, avoiding repeated work present in the brute force recursion. This combination of greedy checks and DP transitions ensures the minimal number of steps while keeping the state space compact.

This pattern appears frequently in string transformation problems where local operations influence global optimality. The DP formulation also mirrors interval and prefix optimization techniques common in dynamic programming problems.

Recommended for interviews: The Greedy + Dynamic Programming approach is the expected solution. Interviewers typically want to see the reasoning from exponential recursion to memoization and then to a clean DP formulation. Mentioning the brute force idea demonstrates understanding of the search space, while the optimized DP shows the ability to eliminate overlapping work and reach an efficient O(n^2) solution.

Solution

We define f[i] as the minimum number of operations required to convert the first i characters of word1 to the first i characters of word2. The answer is f[n], where n is the length of both word1 and word2.

We can compute f[i] by enumerating all possible split points. For each split point j, we need to calculate the minimum number of operations required to convert word1[j:i] to word2[j:i].

We can use a helper function calc(l, r, rev) to compute the minimum number of operations needed to convert word1[l:r] to word2[l:r], where rev indicates whether to reverse the substring. Since the result of performing other operations before or after a reversal is the same, we only need to consider not reversing, and reversing once before other operations. Therefore, f[i] = min_{j < i} (f[j] + min(calc(j, i-1, false), 1 + calc(j, i-1, true))).

Next, we need to implement the calc(l, r, rev) function. We use a 2D array cnt to record the pairing status of characters between word1 and word2. For each character pair (a, b), if a neq b, we check whether cnt[b][a] > 0. If so, we can pair them and reduce one operation; otherwise, we need to add one operation and increment cnt[a][b] by 1.

The time complexity is O(n^3 + |\Sigma|^2) and the space complexity is O(n + |\Sigma|^2), where n is the length of the string and |\Sigma| is the size of the character set (which is 26 in this problem).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(2^n)O(n)Useful for understanding the search space and validating small inputs
Greedy + Dynamic ProgrammingO(n^2)O(n)General case. Efficient for large strings by reusing prefix results

Video Solution

3579. Minimum Steps to Convert String with Operations | LeetCode weekly contest 453 • Amit Dhyani • 832 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Minimum Steps to Convert String with Operations easy or hard?
The problem is classified as Hard because the optimal solution requires recognizing overlapping subproblems and designing the correct DP state transitions. Many candidates initially attempt greedy or brute force strategies before realizing a dynamic programming approach is necessary.
Minimum Steps to Convert String with Operations Python/Java solution
Most implementations follow the same DP pattern regardless of language. Maintain a DP array, iterate through the string, and update the minimum cost for each position using previously computed states. The FleetCode solution provides implementations in Python, Java, C++, Go, TypeScript, and Rust with O(n^2) time complexity.
How to solve Minimum Steps to Convert String with Operations in O(n^2)?
Create a DP array where dp[i] represents the minimum operations required to convert the first i characters. Iterate through the string and evaluate possible operations that end at position i. Combine greedy checks with previously computed DP values to update dp[i]. This reuses subproblem results and ensures the final answer is optimal.
What is the best approach for Minimum Steps to Convert String with Operations?
The most effective solution combines greedy observations with dynamic programming. Define a DP state for the minimum operations needed to convert prefixes of the string and update it by checking valid operations ending at each position. This avoids repeated work from brute force recursion and typically runs in O(n^2) time with O(n) space.
Is Minimum Steps to Convert String with Operations asked at Google/Amazon/Meta?
String transformation problems with dynamic programming appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often involve minimizing operations, segment transformations, or editing costs. Practicing this problem helps build intuition for prefix DP and string optimization patterns.
What data structure is used in Minimum Steps to Convert String with Operations?
The core structure is a dynamic programming array that stores the minimal operations required for each prefix of the string. The algorithm also relies on string traversal and index-based checks to evaluate valid transformations efficiently.
What is the time complexity of Minimum Steps to Convert String with Operations?
The optimized Greedy + Dynamic Programming approach runs in O(n^2) time because each index may evaluate multiple previous breakpoints or operation boundaries. The space complexity is O(n) for the DP array storing the minimum cost for each processed prefix.

Ready to solve this problem?

Practice Minimum Steps to Convert String with Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Edit Distance