Problem

Given two strings initial and target, your task is to modify initial by performing a series of operations to make it equal to target.

In one operation, you can add or remove one character only at the beginning or the end of the string initial.

Return the minimum number of operations required to transform initial into target.

Examples

Example 1:

1
2
3
4
5

Input: initial = "abcde", target = "cdef"
Output: 3
Explanation:
Remove `'a'` and `'b'` from the beginning of `initial`, then add `'f'` to the
end.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: initial = "axxy", target = "yabx"
Output: 6
Explanation:
Operation | Resulting String  
---|---  
Add `'y'` to the beginning | `"yaxxy"`  
Remove from end | `"yaxx"`  
Remove from end | `"yax"`  
Remove from end | `"ya"`  
Add `'b'` to the end | `"yab"`  
Add `'x'` to the end | `"yabx"`

Example 3:

1
2
3
4

Input: initial = "xyz", target = "xyz"
Output: 0
Explanation:
No operations are needed as the strings are already equal.

Constraints:

  • 1 <= initial.length, target.length <= 1000
  • initial and target consist only of lowercase English letters.

Solution

Method 1 – Longest Common Substring at Any Position

Intuition

The only way to transform initial into target using allowed operations is to match a substring of target somewhere in initial and add/remove characters at the ends. The minimum number of operations is the sum of the characters to remove from the ends of initial and the characters to add to match target.

Approach

  1. For all possible substrings of initial, check if it matches any substring of target.
  2. For each match, calculate the number of operations needed:
    • Remove characters from the start and end of initial to get the matching substring.
    • Add characters to the start and end to get to target.
  3. The answer is the minimum number of operations over all possible matches.
  4. If no match, the answer is the length of initial plus the length of target (remove all, add all).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minOperations(string initial, string target) {
        int n = initial.size(), m = target.size(), ans = n + m;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int len = 0;
                while (i + len < n && j + len < m && initial[i + len] == target[j + len]) ++len;
                if (len > 0) {
                    int ops = i + (n - (i + len)) + j + (m - (j + len));
                    ans = min(ans, ops);
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int minOperations(String initial, String target) {
        int n = initial.length(), m = target.length(), ans = n + m;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int len = 0;
                while (i + len < n && j + len < m && initial.charAt(i + len) == target.charAt(j + len)) ++len;
                if (len > 0) {
                    int ops = i + (n - (i + len)) + j + (m - (j + len));
                    ans = Math.min(ans, ops);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minOperations(self, initial: str, target: str) -> int:
        n, m = len(initial), len(target)
        ans = n + m
        for i in range(n):
            for j in range(m):
                l = 0
                while i + l < n and j + l < m and initial[i + l] == target[j + l]:
                    l += 1
                if l > 0:
                    ops = i + (n - (i + l)) + j + (m - (j + l))
                    ans = min(ans, ops)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn min_operations(initial: String, target: String) -> i32 {
        let n = initial.len();
        let m = target.len();
        let initial = initial.as_bytes();
        let target = target.as_bytes();
        let mut ans = (n + m) as i32;
        for i in 0..n {
            for j in 0..m {
                let mut l = 0;
                while i + l < n && j + l < m && initial[i + l] == target[j + l] {
                    l += 1;
                }
                if l > 0 {
                    let ops = i + (n - (i + l)) + j + (m - (j + l));
                    ans = ans.min(ops as i32);
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minOperations(initial: string, target: string): number {
        const n = initial.length, m = target.length;
        let ans = n + m;
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < m; ++j) {
                let l = 0;
                while (i + l < n && j + l < m && initial[i + l] === target[j + l]) ++l;
                if (l > 0) {
                    const ops = i + (n - (i + l)) + j + (m - (j + l));
                    ans = Math.min(ans, ops);
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 m^2) in the worst case, but typically much faster for practical strings.
  • 🧺 Space complexity: O(1).