Skip to content

3135. Equalize Strings by Adding or Removing Characters at Ends πŸ”’

Description

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.

 

Example 1:

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:

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:

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.

Solutions

Solution 1: Dynamic Programming

Thinking

Only prefixes and suffixes may be deleted or appended, so a contiguous common substring must be kept. Testing every substring of \(initial\) inside \(target\) is \(O(m^2n)\).

The operation count is the discarded prefix/suffix of \(initial\) plus the missing sides of \(target\), i.e. \(m+n-2\cdot mx\) for the longest common substring length \(mx\).

Standard DP: \(f[i][j]\) is the common substring ending at \(initial[i-1]\) and \(target[j-1]\), extending when the letters match. The answer uses the global maximum \(mx\).

Let's assume that the lengths of the strings initial and target are \(m\) and \(n\), respectively.

According to the problem description, we only need to find the length \(mx\) of the longest common substring of initial and target. Then, we can delete \(m - mx\) characters from initial and add \(n - mx\) characters to transform initial into target. Therefore, the answer is \(m + n - 2 \times mx\).

We can use dynamic programming to find the length \(mx\) of the longest common substring of initial and target. We define a two-dimensional array \(f\), where \(f[i][j]\) represents the length of the longest common substring ending with initial[i - 1] and target[j - 1]. Then, we can get the state transition equation:

\[ f[i][j] = \begin{cases} f[i - 1][j - 1] + 1, & \textit{if } \textit{initial}[i - 1] = \textit{target}[j - 1], \\ 0, & \textit{otherwise}. \end{cases} \]

Then \(mx = \max f[i][j]\), and the final answer is \(m + n - 2 \times mx\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Where \(m\) and \(n\) are the lengths of the strings initial and target, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minOperations(self, initial: str, target: str) -> int:
        m, n = len(initial), len(target)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        mx = 0
        for i, a in enumerate(initial, 1):
            for j, b in enumerate(target, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1] + 1
                    mx = max(mx, f[i][j])
        return m + n - mx * 2

 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 m = initial.length(), n = target.length();
        int[][] f = new int[m + 1][n + 1];
        int mx = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (initial.charAt(i - 1) == target.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    mx = Math.max(mx, f[i][j]);
                }
            }
        }
        return m + n - 2 * mx;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minOperations(string initial, string target) {
        int m = initial.size(), n = target.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof(f));
        int mx = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (initial[i - 1] == target[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    mx = max(mx, f[i][j]);
                }
            }
        }
        return m + n - 2 * mx;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func minOperations(initial string, target string) int {
    m, n := len(initial), len(target)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    mx := 0
    for i, a := range initial {
        for j, b := range target {
            if a == b {
                f[i+1][j+1] = f[i][j] + 1
                mx = max(mx, f[i+1][j+1])
            }
        }
    }
    return m + n - 2*mx
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function minOperations(initial: string, target: string): number {
    const m = initial.length;
    const n = target.length;
    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    let mx: number = 0;
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (initial[i - 1] === target[j - 1]) {
                f[i][j] = f[i - 1][j - 1] + 1;
                mx = Math.max(mx, f[i][j]);
            }
        }
    }
    return m + n - 2 * mx;
}

Comments