Minimum Steps to Convert String with Operations

Minimum Steps to Convert String with Operations - 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:

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.

Input & Output

Example 1 — Basic Swap

$ Input: word1 = "ab", word2 = "ba"

› Output: 1

💡 Note: We can transform "ab" to "ba" with a single swap operation on the entire string.

Example 2 — Multiple Operations

$ Input: word1 = "abc", word2 = "bca"

› Output: 2

💡 Note: We can divide into substrings: "a" (replace to "b") costs 1, "bc" (reverse to "cb" then replace c→c, b→a) or use 2 replacements total.

Example 3 — Already Equal

$ Input: word1 = "hello", word2 = "hello"

› Output: 0

💡 Note: The strings are already identical, so no operations are needed.

Constraints

1 ≤ word1.length, word2.length ≤ 1000
word1.length == word2.length
word1 and word2 consist of only lowercase English letters

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is to optimally partition strings and choose between replace, swap, and reverse operations. The greedy approach provides good practical performance with O(n²) time complexity by making locally optimal choices at each position.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Optimization	O(n²)	O(1)	Make locally optimal choices for each substring to minimize total operations
Brute Force Recursive	O(3^n)	O(n)	Try all possible substring divisions and operation combinations
Dynamic Programming with Memoization	O(n² × 2^n)	O(n)	Cache results of subproblems to avoid recomputation

Greedy Optimization — Algorithm Steps

Scan left to right through strings
For each position, try substring lengths up to a reasonable limit
Choose the operation (replace/swap/reverse) that minimizes cost
Move to next unprocessed position

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Position

Check current position and try different substring lengths

Evaluate Operations

Test replace, swap, and reverse operations for best cost

Make Greedy Choice

Choose operation with minimum cost and advance position

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void reverseString(char* str, int length) {
    for (int i = 0; i < length / 2; i++) {
        char temp = str[i];
        str[i] = str[length - 1 - i];
        str[length - 1 - i] = temp;
    }
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(char* word1, char* word2) {
    int n = strlen(word1);
    int i = 0;
    int operations = 0;
    
    while (i < n) {
        if (word1[i] == word2[i]) {
            i++;
            continue;
        }
        
        int bestCost = 1;  // Replace operation
        int bestLength = 1;
        
        // Try different substring lengths
        for (int length = 1; length <= min(n - i, 10); length++) {
            char substr1[length + 1], substr2[length + 1];
            strncpy(substr1, word1 + i, length);
            strncpy(substr2, word2 + i, length);
            substr1[length] = '\0';
            substr2[length] = '\0';
            
            if (strcmp(substr1, substr2) == 0) {
                bestCost = 0;
                bestLength = length;
                break;
            }
            
            // Try reverse
            char reversed[length + 1];
            strcpy(reversed, substr1);
            reverseString(reversed, length);
            if (strcmp(reversed, substr2) == 0) {
                bestCost = 1;
                bestLength = length;
                break;
            }
            
            // Try single swap for length 2
            if (length == 2) {
                char swapped[3];
                swapped[0] = substr1[1];
                swapped[1] = substr1[0];
                swapped[2] = '\0';
                if (strcmp(swapped, substr2) == 0) {
                    bestCost = 1;
                    bestLength = 2;
                    break;
                }
            }
            
            // Check replacement cost
            int replacements = 0;
            for (int j = 0; j < length; j++) {
                if (substr1[j] != substr2[j]) replacements++;
            }
            if (replacements < bestCost) {
                bestCost = replacements;
                bestLength = length;
            }
        }
        
        operations += bestCost;
        i += bestLength;
    }
    
    return operations;
}

int main() {
    char word1[1001], word2[1001];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    
    printf("%d\n", solution(word1, word2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position, check substring lengths up to n, with constant work per substring

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures needed

✓ Linear Space

12.3K Views

Medium Frequency

~35 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler