Equalize Strings by Adding or Removing Characters at Ends - Solution & Explanation

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.