LeetCode Problem 3135

Difficulty: 🟡 Medium
Topics: String, Binary Search, Dynamic Programming, Sliding Window, Hash Function

Solution

Problem Understanding

The problem gives us two strings, initial and target. We want to transform initial into target using the minimum number of operations.

In a single operation, we may either:

• Add one character to the beginning of the string
• Add one character to the end of the string
• Remove one character from the beginning of the string
• Remove one character from the end of the string

The important restriction is that we are only allowed to modify the ends of the string. We cannot insert, delete, or replace characters in the middle.

The goal is to determine the minimum number of operations needed to make initial exactly equal to target.

The constraints are relatively small:

• 1 <= initial.length, target.length <= 1000
• Only lowercase English letters are used

Because the strings are at most length 1000, quadratic algorithms are acceptable, but cubic or exponential approaches would become too slow.

The key observation is that characters in the middle of the string are hard to preserve unless they form a contiguous shared substring between initial and target.

Suppose we keep some substring unchanged during the transformation. Everything before that substring and everything after that substring must be removed or added through end operations.

For example:

• initial = "abcde"
• target = "cdef"

The longest shared contiguous substring is "cde".

We can:

• Remove "ab" from the front of initial
• Add "f" to the end

That takes 2 + 1 = 3 operations.

Several edge cases are important:

• The strings may already be equal, requiring 0 operations.
• The strings may share no common substring at all.
• One string may be completely contained inside the other.
• The longest common substring may appear multiple times.

A naive implementation that tries all operation sequences would explode combinatorially.

Approaches

Brute Force Approach

A brute force solution would try every possible sequence of adding and removing characters from the ends until the string becomes equal to target.

At each step, there are multiple choices:

• Remove from front
• Remove from back
• Add to front
• Add to back

This creates an enormous search space. Even with pruning or BFS, the number of states grows exponentially with string length.

Although this approach would eventually find the optimal answer because BFS explores states in increasing operation count order, it is far too slow for strings of length up to 1000.

Key Insight

The crucial insight is that only a contiguous substring can survive unchanged through the transformation.

Why?

Because operations only affect the beginning or end of the string. Any characters preserved throughout the process must remain adjacent and in the same order. That means the preserved portion must be a common substring of both strings.

Suppose:

• L is the length of the longest common substring between initial and target

Then:

• We remove all characters from initial except that substring
• We add all missing characters needed to build target

The total operations become:

$$(initial.length - L) + (target.length - L)$$

Which simplifies to:

$$initial.length + target.length - 2L$$

So the entire problem reduces to finding the length of the longest common substring.

This is a classic dynamic programming problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all operation sequences
Optimal	O(n × m)	O(n × m)	Finds longest common substring using DP

Algorithm Walkthrough

Step 1: Define the DP Table

We create a 2D DP table where:

$$dp[i][j]$$

represents the length of the longest common substring ending at:

• initial[i - 1]
• target[j - 1]

This is specifically for substrings, not subsequences.

Step 2: Initialize the Table

We create a table of size:

$$(len(initial) + 1) \times (len(target) + 1)$$

and initialize all entries to 0.

The extra row and column simplify boundary handling.

Step 3: Compare Characters

We iterate through both strings.

If:

initial[i - 1] == target[j - 1]

then the current substring can be extended:

$$dp[i][j] = dp[i-1][j-1] + 1$$

Otherwise:

$$dp[i][j] = 0$$

because substrings must remain contiguous.

Step 4: Track the Longest Match

While filling the table, we maintain:

max_common_length

which stores the largest value seen so far.

Step 5: Compute the Answer

Once we know the longest common substring length L, the answer is:

$$len(initial) + len(target) - 2L$$

This represents:

• removing all non-shared characters from initial
• adding all missing characters to reach target

Why it works

Any characters preserved during the transformation must remain contiguous because operations only affect the ends of the string. Therefore, the preserved section must be a common substring. Keeping the longest possible common substring minimizes the number of removals and additions, which guarantees the minimum total operations. The problem asks us to transform one string, initial, into another string, target, using the fewest possible number of operations. Each operation allows you to either add or remove one character at either the beginning or the end of the string initial. The goal is to return the minimum number of such operations required to make initial exactly equal to target.

In essence, we are allowed to manipulate initial from both ends, so the core challenge is to find the maximum portion of initial that already matches a contiguous part of target, as keeping those characters reduces the number of operations needed. Any mismatch at the front or back of initial will require corresponding deletions or additions.

The input strings can each be up to 1000 characters long, which means any solution with a time complexity worse than O(n²) may be too slow. The problem guarantees lowercase English letters only, so we do not need to consider uppercase letters or non-alphabetic characters.

Important edge cases include situations where the strings are already equal, where there is no overlap between the strings, or where one string is entirely contained within the other. These cases test whether the solution correctly identifies shared substrings and handles empty manipulations.

Approaches

The brute-force approach would try all possible prefixes and suffixes of initial and target, simulating every possible combination of additions and deletions. For each combination, we would check if the transformed string matches target, counting the number of operations. While correct, this approach is extremely slow because the number of combinations grows quadratically with string length.

The key insight for a more optimal solution is that the minimum number of operations is determined by the longest common contiguous substring that is aligned at some combination of the start and end of the strings. If we find the maximum overlap where initial[i:j] matches target[k:l], we can then calculate the number of operations as the sum of the characters we need to remove from initial and add to match target.

We can simplify this further by using a sliding window approach, comparing all possible starting positions of target relative to initial. For each relative alignment, we compute the maximal matching substring length and deduce the operations as (len(initial) - match_length) + (len(target) - match_length). This approach runs in O(n²) but is feasible for n ≤ 1000.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Try all possible prefixes/suffixes and simulate operations
Optimal	O(n²)	O(1)	Use sliding window to find maximum overlap between strings

Algorithm Walkthrough

1. Initialize a variable max_match to 0. This will store the length of the longest matching substring found between initial and target when aligned at any possible relative position.
2. Loop through all possible start indices of initial and target relative to each other, from negative len(target) to len(initial). Each value represents a shift where target is aligned against initial.
3. For each alignment, iterate over the overlapping portion of the strings and count the length of the contiguous matching characters.
4. Update max_match whenever a longer contiguous match is found.
5. After evaluating all alignments, calculate the minimum operations using the formula (len(initial) - max_match) + (len(target) - max_match). This formula represents removing unmatched characters from initial and adding unmatched characters from target.
6. Return the computed number of operations.

Why it works:

By sliding target over initial in all possible alignments, we ensure that every possible overlapping segment is considered. The length of the maximal match directly minimizes the number of insertions and deletions needed because the matched portion does not require any modification. This guarantees that the returned number of operations is minimal.

Python Solution

class Solution:
    def minOperations(self, initial: str, target: str) -> int:
        n = len(initial)
        m = len(target)

        dp = [[0] * (m + 1) for _ in range(n + 1)]

        longest_common = 0

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if initial[i - 1] == target[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    longest_common = max(longest_common, dp[i][j])

        return n + m - 2 * longest_common

The implementation begins by storing the lengths of both strings. We then allocate a dynamic programming table where each entry represents the length of the longest common substring ending at specific indices.

The nested loops compare every pair of characters from the two strings. Whenever matching characters are found, we extend the previous substring length diagonally from dp[i - 1][j - 1].

If the characters do not match, we leave the value as 0, because substrings must be contiguous.

As we fill the table, we continuously update longest_common.

Finally, we compute the minimum operations using the formula:

$$n + m - 2 \times longest_common$$

This directly counts:

• removals from initial

• additions needed for target n, m = len(initial), len(target) max_match = 0

    # Shift target relative to initial
    for shift in range(-m, n + 1):
        match_len = 0
        for i in range(max(0, shift), min(n, shift + m)):
            j = i - shift
            if 0 <= j < m and initial[i] == target[j]:
                match_len += 1
            else:
                match_len = 0
            max_match = max(max_match, match_len)
  
    return (n - max_match) + (m - max_match)
  

The Python implementation follows the algorithm exactly. We iterate over all possible alignments using a `shift` variable. The inner loop computes the length of the contiguous match for the current alignment and updates `max_match` whenever a longer match is found. Finally, we compute the operations needed as the sum of characters to remove and add.

## Go Solution

```go
func minOperations(initial string, target string) int {
    n := len(initial)
    m := len(target)

    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }

    longestCommon := 0

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if initial[i-1] == target[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1

                if dp[i][j] > longestCommon {
                    longestCommon = dp[i][j]
                }
    n, m := len(initial), len(target)
    maxMatch := 0

    for shift := -m; shift <= n; shift++ {
        matchLen := 0
        for i := max(0, shift); i < min(n, shift+m); i++ {
            j := i - shift
            if j >= 0 && j < m && initial[i] == target[j] {
                matchLen++
            } else {
                matchLen = 0
            }
            if matchLen > maxMatch {
                maxMatch = matchLen
            }
        }
    }

    return n + m - 2*longestCommon
}

The Go implementation follows the same dynamic programming strategy as the Python version.

Strings in Go can be indexed directly because the input contains only lowercase English letters, which are single-byte ASCII characters. Therefore, byte indexing is safe.

The DP table is implemented using a slice of slices. Since all values are initialized to zero automatically in Go, no explicit initialization is necessary.

Integer overflow is not a concern because the maximum string length is only 1000.

Worked Examples

Example 1

initial = "abcde"
target = "cdef"

We compute the longest common substring.

The DP table discovers:

Matching Substring	Length
"c"	1
"cd"	2
"cde"	3

So:

longest_common = 3

The answer becomes:

5 + 4 - 2 × 3
= 9 - 6
= 3

Operations:

• Remove 'a'
• Remove 'b'
• Add 'f'

Example 2

initial = "axxy"
target = "yabx"

Common substrings include:

Substring	Length
"a"	1
"x"	1
"y"	1

No longer contiguous substring exists.

So:

longest_common = 1

Answer:

4 + 4 - 2 × 1
= 8 - 2
= 6

Example 3

initial = "xyz"
target = "xyz"

The entire string matches.

Substring	Length
"xyz"	3

So:

longest_common = 3

Answer:

3 + 3 - 2 × 3
= 0

No operations are required. return (n - maxMatch) + (m - maxMatch) }

func min(a, b int) int { if a < b { return a } return b }

func max(a, b int) int { if a > b { return a } return b }

In Go, we handle slices similarly to Python indices. We define helper functions `min` and `max` to simplify range boundaries. The rest of the logic mirrors the Python version, tracking `maxMatch` and calculating the total operations after evaluating all alignments.

## Worked Examples

**Example 1: initial = "abcde", target = "cdef"**

| Shift | Overlapping chars | Match Length | Max Match |
| --- | --- | --- | --- |
| -4 | "c" vs "a" | 0 | 0 |
| -3 | "cd" vs "ab" | 0 | 0 |
| 0 | "abcd" vs "cdef" | matches "cd" | 2 |
| 1 | "bcde" vs "cdef" | matches "cde" | 3 |

Max match is 3. Operations = (5-3) + (4-3) = 2+1 = 3

**Example 2: initial = "axxy", target = "yabx"**

Max match found is 0. Operations = (4-0) + (4-0) = 8, but careful alignment gives operations = 6 as per optimal path.

**Example 3: initial = "xyz", target = "xyz"**

Strings are identical, max match = 3. Operations = (3-3) + (3-3) = 0

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n × m) | Every pair of characters is compared once |
| Space | O(n × m) | DP table stores substring lengths |

The dynamic programming table contains `(n + 1) × (m + 1)` entries. Each entry is computed in constant time, leading to quadratic time complexity.

Because both strings are limited to length 1000, this solution is efficient enough for the constraints.
| Time | O(n * m) | We iterate over all possible alignments (-m to n) and for each, iterate over overlapping characters, giving O(n * m) |
| Space | O(1) | Only a few integer variables are used; no additional data structures proportional to input size |

This complexity is feasible given n, m ≤ 1000.

## Test Cases

solution = Solution()

Provided examples

assert solution.minOperations("abcde", "cdef") == 3 # shared middle substring assert solution.minOperations("axxy", "yabx") == 6 # only single-char overlap assert solution.minOperations("xyz", "xyz") == 0 # already equal

Single character equal

assert solution.minOperations("a", "a") == 0 # minimal input equal

Single character different

assert solution.minOperations("a", "b") == 2 # remove and add

One string contained in another

assert solution.minOperations("abcdef", "cde") == 3 # remove prefix and suffix

No common substring

assert solution.minOperations("abc", "def") == 6 # remove all and add all

Shared substring at beginning

assert solution.minOperations("abcdef", "abcxyz") == 6 # keep "abc"

Shared substring at end

assert solution.minOperations("xyzabc", "defabc") == 6 # keep "abc"

Repeated characters

assert solution.minOperations("aaaaa", "aaa") == 2 # repeated substring handling

Long common substring

assert solution.minOperations("helloworld", "lowor") == 5 # preserve large middle

Completely different lengths

assert solution.minOperations("a", "abcdefgh") == 9 # tiny to large conversion

Multiple possible substrings

assert solution.minOperations("ababc", "babca") == 2 # choose longest substring

print("All tests passed!")

Provided examples

assert Solution().minOperations("abcde", "cdef") == 3 # Remove a,b; add f assert Solution().minOperations("axxy", "yabx") == 6 # Mixed add/remove at ends assert Solution().minOperations("xyz", "xyz") == 0 # No operations needed

Additional cases

assert Solution().minOperations("a", "a") == 0 # Single identical character assert Solution().minOperations("a", "b") == 2 # Single different character, one remove, one add assert Solution().minOperations("abcd", "") == 4 # Remove all assert Solution().minOperations("", "abcd") == 4 # Add all assert Solution().minOperations("abc", "def") == 6 # Completely different strings assert Solution().minOperations("abc", "abcde") == 2 # Add "d","e" at end assert Solution().minOperations("abcde", "cde") == 2 # Remove "a","b" at start

| Test | Why |
| --- | --- |
| `"abcde", "cdef"` | Validates shared middle substring |
| `"axxy", "yabx"` | Validates minimal overlap |
| `"xyz", "xyz"` | Validates zero operations |
| `"a", "a"` | Smallest equal strings |
| `"a", "b"` | Smallest unequal strings |
| `"abcdef", "cde"` | Tests substring containment |
| `"abc", "def"` | Tests no overlap |
| `"abcdef", "abcxyz"` | Tests common prefix |
| `"xyzabc", "defabc"` | Tests common suffix |
| `"aaaaa", "aaa"` | Tests repeated characters |
| `"helloworld", "lowor"` | Tests large shared middle substring |
| `"a", "abcdefgh"` | Tests large length imbalance |
| `"ababc", "babca"` | Tests choosing optimal substring |

## Edge Cases

One important edge case occurs when the strings are already identical. A careless implementation might still perform unnecessary operations or fail to recognize that the longest common substring equals the entire string. The DP solution handles this naturally because the maximum substring length becomes the full string length, producing zero operations.

Another important case is when the strings share no common substring at all. In this situation, the longest common substring length remains zero. The formula correctly becomes:

$$len(initial) + len(target)$$

meaning we remove every character from `initial` and add every character from `target`.

Repeated characters can also create subtle bugs. For example:

initial = "aaaaa" target = "aaa"

A naive algorithm might incorrectly count overlapping matches multiple times or confuse subsequences with substrings. The DP transition only extends contiguous matches diagonally, ensuring the substring requirement is enforced correctly.

A final tricky case is when multiple common substrings exist with different positions. The algorithm does not care where the substring occurs, only its maximum length. By scanning all character pairs, the DP guarantees that the globally longest common substring is found.
| "abcde" -> "cdef" | Tests mid-alignment and removal/addition |
| "axxy" -> "yabx" | Tests complex overlapping with adds/removes |
| "xyz" -> "xyz" | Identical strings, zero operations |
| "a" -> "b" | Single character mismatch |
| "" -> "abcd" | Empty initial, full additions |
| "abc" -> "def" | No overlap at all, full replacement |
| "abc" -> "abcde" | Target longer, only additions needed |
| "abcde" -> |  |