Equalize Strings by Adding or Removing Characters at Ends

Equalize Strings by Adding or Removing Characters at Ends - 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.

Input & Output

Example 1 — Basic Transformation

$ Input: initial = "abc", target = "ac"

› Output: 1

💡 Note: Remove 'b' from the middle by removing it from either end after rearranging. Actually, we can keep 'a' and 'c', so we need to remove 'b' (1 operation).

Example 2 — Complete Replacement

$ Input: initial = "abc", target = "def"

› Output: 6

💡 Note: No common characters, so remove all 3 characters from initial (3 ops) and add all 3 characters for target (3 ops) = 6 operations total.

Example 3 — Partial Overlap

$ Input: initial = "abcde", target = "cdefg"

› Output: 4

💡 Note: Keep common substring 'cde' (length 3). Remove 'ab' (2 ops) + add 'fg' (2 ops) = 4 operations.

Constraints

0 ≤ initial.length, target.length ≤ 1000
initial and target consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Strings

initial and target strings

Find Overlap

Determine maximum characters to keep

Calculate Operations

Minimum operations needed

Key Takeaway

🎯 Key Insight: Find the longest common subsequence to maximize characters we can keep unchanged

Asked in

G Google 35 f Facebook 28 a Amazon 22

The key insight is to find the maximum characters we can keep unchanged and minimize the operations. The optimal approach uses Longest Common Subsequence (LCS) to find the maximum overlap. Time: O(n×m), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Longest Common Subsequence Approach	O(n×m)	O(n×m)	Use dynamic programming to find longest common subsequence, then calculate minimum operations
Try All Operation Sequences	O(4^(n+m))	O(4^(n+m))	Generate all possible operation sequences until target is reached
Find Maximum Overlap	O(n×m²)	O(1)	Find the longest substring of target that appears in initial to minimize operations

Longest Common Subsequence Approach — Algorithm Steps

Create DP table for LCS
Fill table using standard LCS algorithm
LCS length gives maximum characters we can keep
Return (initial_len + target_len - 2×LCS)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP Table

Create (n+1)×(m+1) table

Fill Table

Use LCS recurrence relation

Calculate Result

Operations = n + m - 2×LCS

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(char* initial, char* target) {
    int n = strlen(initial), m = strlen(target);
    
    int** dp = malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = calloc(m + 1, sizeof(int));
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (initial[i-1] == target[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    int result = n + m - 2 * dp[n][m];
    
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    char initial[1001], target[1001];
    fgets(initial, sizeof(initial), stdin);
    fgets(target, sizeof(target), stdin);
    
    initial[strcspn(initial, "\n")] = 0;
    target[strcspn(target, "\n")] = 0;
    
    printf("%d\n", solution(initial, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

DP table of size n×m, each cell computed once

✓ Linear Growth

Space Complexity

O(n×m)

DP table stores n×m values

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Longest Common Subsequence Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler