Equalize Strings by Adding or Removing Characters at Ends - Solution & Explanation
Problem Statement
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 <= 1000initialandtargetconsist only of lowercase English letters.
Approach Overview
Problem Overview: Two strings are given. You can only add characters to the beginning or end of a string, or remove characters from the beginning or end. The goal is to make both strings identical using the minimum number of operations.
The key restriction is operations only happen at the ends. That means the portion of the string that remains unchanged must be a contiguous substring. If both strings share a common substring in the middle, you can remove everything outside that substring and the strings become equal. The optimal strategy is therefore to keep the longest common substring between the two strings.
Approach 1: Dynamic Programming - Longest Common Substring (O(n * m) time, O(n * m) space)
Compute the longest common substring between the two strings using a classic Dynamic Programming table. Create a 2D DP array where dp[i][j] stores the length of the longest common suffix ending at s[i-1] and t[j-1]. If the characters match, extend the previous substring using dp[i][j] = dp[i-1][j-1] + 1. If they differ, reset to zero because substrings must stay contiguous.
Track the maximum value found in the table. That value is the length of the longest common substring L. Once you know L, the minimum operations required is (n - L) + (m - L), where n and m are the lengths of the two strings. These operations correspond to removing extra characters from the ends until both strings match the shared substring. This approach is straightforward, reliable, and commonly expected in interviews.
Approach 2: Binary Search + Rolling Hash (O((n + m) log(min(n,m))) time, O(n + m) space)
You can also solve this using Binary Search combined with a Hash Function (Rabin–Karp style). Binary search on the length of the common substring. For each candidate length k, compute rolling hashes for all substrings of length k in the first string and store them in a hash set. Then slide a window of size k over the second string and check if any hash matches.
If a match exists, a common substring of length k exists, so increase the search range. Otherwise reduce it. This method avoids the full DP table and works well for long strings. Internally it uses substring hashing and a Sliding Window to update hashes efficiently.
Recommended for interviews: The dynamic programming longest common substring approach is the safest explanation during interviews. It clearly shows understanding of substring constraints and DP state transitions. The binary search + rolling hash optimization is useful when input sizes are large, but interviewers usually expect the DP formulation first.
Solution
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, & if initial[i - 1] = target[j - 1], \
0, & 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.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Longest Common Substring) | O(n * m) | O(n * m) | General case and most interview settings where clarity is preferred |
| Space Optimized DP | O(n * m) | O(min(n,m)) | When memory usage matters but DP approach is still desired |
| Binary Search + Rolling Hash | O((n + m) log(min(n,m))) | O(n + m) | Large strings where DP table becomes expensive |
Video Solution
3135. Equalize Strings by Adding or Removing Characters at Ends (Leetcode Medium) • Programming Live with Larry • 209 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Equalize Strings by Adding or Removing Characters at Ends easy or hard?
Equalize Strings by Adding or Removing Characters at Ends Python/Java solution
How to solve Equalize Strings by Adding or Removing Characters at Ends in O(n)?
What is the best approach for Equalize Strings by Adding or Removing Characters at Ends?
Is Equalize Strings by Adding or Removing Characters at Ends asked at Google/Amazon/Meta?
What data structure is used in Equalize Strings by Adding or Removing Characters at Ends?
What is the time complexity of Equalize Strings by Adding or Removing Characters at Ends?
Ready to solve this problem?
Practice Equalize Strings by Adding or Removing Characters at Ends with our built-in code editor and test cases.
Practice on FleetCode