Transform One String to Another using Minimum Number of Given Operation

Problem Statement

Given two strings A and B, find the minimum number of operations required to transform A into B using only the following operations:

• Delete a character
• Insert a character

Both operations can only be performed on string A. Alternatively, the problem can be stated as: only deletion is allowed, and we can rearrange characters.

Example:

• Input: A = "ABD", B = "BAD"
• Output: 1
• Explanation: Delete 'A' from position 0, insert at position 1

Note: This is different from standard edit distance. Here we're checking if transformation is possible by rearranging + adding/removing characters.

Approach 1: Check Character Counts

Intuition

For transformation to be possible:

1. Every character in B must exist in A (we can only delete from A, so B's chars must come from A)
2. If frequencies match, we can rearrange
3. If A has extra characters, we delete them

Algorithm

1. Count frequencies in both strings
2. Check if B has any character not in A (impossible if so)
3. Count deletions needed = |A| - |B|
4. For rearrangement, count position mismatches

import java.util.*;

public class Solution {
    public int minOperations(String A, String B) {
        Map<Character, Integer> countA = new HashMap<>();
        Map<Character, Integer> countB = new HashMap<>();
        
        for (char c : A.toCharArray()) {
            countA.put(c, countA.getOrDefault(c, 0) + 1);
        }
        for (char c : B.toCharArray()) {
            countB.put(c, countB.getOrDefault(c, 0) + 1);
        }
        
        for (Map.Entry<Character, Integer> e : countB.entrySet()) {
            if (countA.getOrDefault(e.getKey(), 0) < e.getValue()) {
                return -1;
            }
        }
        
        return A.length() - B.length();
    }
}

Complexity Analysis

• Time Complexity: O(n + m) - Counting characters
• Space Complexity: O(1) - At most 26 characters for lowercase alphabet

Approach 2: Using Longest Common Subsequence

Intuition

The minimum operations = deletions from A + insertions to get B

• Deletions from A = |A| - LCS(A, B)
• Insertions needed = |B| - LCS(A, B)
• Total = |A| + |B| - 2 * LCS(A, B)

But if only deletions allowed (and implicit rearrangement):

• Answer = |A| - |B| if B's chars are subset of A's chars

public class Solution {
    private int lcs(String A, String B) {
        int n = A.length(), m = B.length();
        int[][] dp = new int[n + 1][m + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i-1) == B.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        return dp[n][m];
    }
    
    public int minOperations(String A, String B) {
        int lcsLen = lcs(A, B);
        return A.length() + B.length() - 2 * lcsLen;
    }
}

Complexity Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m), can be optimized to O(min(n, m))

Approach 3: Specific Transformation Problem

If the problem specifically asks: "Can we transform A to B by only deleting characters and the remaining characters automatically rearrange?"

BFS Approach (For Finding Minimum Operations Sequence)

If we need the actual sequence of operations:

This BFS approach has exponential complexity and is not practical for large strings.

Key Takeaways

1. Character frequency determines if transformation is possible
2. LCS approach gives minimum operations for delete + insert
3. If only deletions allowed: answer = excess characters in A
4. The problem has many variations - clarify exact constraints
5. Related: Edit Distance, Delete Operation for Two Strings (LeetCode 583)
6. BFS is impractical for this problem due to state explosion