String Reconfiguration — Problem Statement & Solution Guide
Problem Description
Given two strings S and T, compute the minimum number of edit operations required to transform S into T. An edit operation can be an insertion of a single character, a deletion of a single character, or a substitution of one character for another. The strings may contain any Unicode characters, including emojis and special symbols. The task is to output the smallest possible count of such operations.
Input consists of two lines: the first line contains S, the second line contains T. Each string may be empty. Output a single integer representing the minimal edit distance between the two strings.
DSA Pattern Breakdown
DSA Pattern Breakdown
"String Reconfiguration"
WHY DOES IT MATTER?
Edit Distance is a foundational DP pattern that teaches the decomposition of string problems into overlapping subproblems. It is essential for understanding how to handle state transitions in sequences, which is critical for bioinformatics (DNA alignment), spell-checkers, and diff algorithms in version control systems.
OPTIMIZATION CHALLENGE
The key insight is that the DP table is filled in a way that each cell only depends on the previous row and the current row's previous column. This allows us to discard the entire previous row after processing, reducing space complexity from O(N*M) to O(min(N, M)).
REAL-WORLD CONNECTION
This algorithm is the engine behind Git's diff tool, which calculates the minimum number of changes to transform one version of a file into another. It is also used in spell-checkers to suggest corrections and in bioinformatics to align DNA sequences to identify genetic similarities.
Always check if the strings are empty or if one is a prefix of the other. If S is a prefix of T, the answer is simply len(T) - len(S). This early exit can save significant computation time in edge cases.
COMPLEXITY AT A GLANCE
O(n*m)O(n*m)Core Theory — Why This Approach?
The problem of transforming string S into string T with minimum edit operations is a classic application of Dynamic Programming (DP), specifically known as the Levenshtein Distance or Edit Distance. The core intuition is that the optimal solution for transforming the first i characters of S into the first j characters of T depends on the optimal solutions for smaller subproblems. We define a 2D DP table dp[i][j] where the value represents the minimum cost to convert S[0..i-1] to T[0..j-1]. The recurrence relation considers three cases: if the last characters match, no operation is needed (dp[i][j] = dp[i-1][j-1]); if they don't match, we take the minimum of three operations: substitution (dp[i-1][j-1] + 1), deletion from S (dp[i-1][j] + 1), or insertion into S (dp[i][j-1] + 1). This approach ensures we explore all possible paths of edits while avoiding redundant calculations by storing intermediate results.
Interview Questions on This Problem
Q1At a fintech platform, we need to detect typos in transaction descriptions to flag potential fraud. How would you adapt the standard Edit Distance algorithm to handle weighted costs where deleting a digit is more expensive than substituting a letter?
Modify the DP recurrence to use specific cost variables instead of hardcoded 1s. Define cost_sub, cost_del, and cost_ins. When characters differ, the substitution cost is dp[i-1][j-1] + cost_sub. Deletion is dp[i-1][j] + cost_del, and insertion is dp[i][j-1] + cost_ins. This allows the algorithm to prioritize cheaper operations, reflecting business logic where certain errors are more critical than others.
Q2In a high-growth startup's search engine, we need to find the closest match in a dictionary of 100,000 words for a user's typo. Computing full Edit Distance for every word is too slow. How can you optimize this?
Use a Trie (Prefix Tree) combined with DFS and pruning. As you traverse the Trie, maintain the current edit distance. If the current distance exceeds the threshold (e.g., 2), prune that branch. Additionally, use the property that if the remaining characters in the target string are fewer than the current distance, you can stop early. This reduces the average case complexity significantly compared to O(N*M) for each word.
Q3For a distributed system logging service, we need to compare two large log strings (10,000 chars each) to determine if they are 'similar' (distance < 5). The standard O(N*M) DP table uses too much memory. How do you solve this?
Use the Hirschberg algorithm or a space-optimized DP that only keeps two rows (current and previous) since dp[i][j] only depends on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. This reduces space complexity from O(N*M) to O(min(N, M)). For very large strings with a small distance threshold, you can also use the 'banded' DP approach, only computing cells within a diagonal band of width 2*threshold, reducing time complexity to O(N * threshold).
Examples
Input
kitten sitting
Output
3
Explanation: 1) Substitute 'k' with 's' → sitten 2) Substitute 'e' with 'i' → sittin 3) Insert 'g' at the end → sitting Total operations: 3
Input
flaw lawn
Output
2
Explanation: 1) Delete 'f' → law 2) Insert 'n' at the end → lawn Total operations: 2
Input
😀😃😄 😃😄😅
Output
2
Explanation: 1) Delete the first emoji '😀' → 😃😄 2) Insert '😅' at the end → 😃😄😅 Total operations: 2
Constraints
- 1 <= |S|, |T| <= 100000
- S and T may contain any Unicode code point
- The algorithm must run in O(|S| + |T|) time and O(min(|S|,|T|)) space
Optimal Approach & Strategy
The optimized approach uses dynamic programming to build a 2D matrix, where each cell represents the minimum number of operations required to transform the first i characters of the first string into the first j characters of the second string. This approach has a time complexity of O(n*m), where n and m are the lengths of the two strings.
Brute Force Approach
The brute-force approach involves trying all possible combinations of operations (insertions, deletions, substitutions) and selecting the combination that results in the fewest operations. This approach has a time complexity of O(3^n), where n is the length of the first string.
Verified Code Solutions
function minOperations(str1, str2) {
const m = str1.length;
const n = str2.length;
const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i === 0) {
dp[i][j] = j;
} else if (j === 0) {
dp[i][j] = i;
} else if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minOperations(string str1, string str2) {
int m = str1.size();
int n = str2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
if (i == 0) {
dp[i][j] = j; // insert all characters of str2
} else if (j == 0) {
dp[i][j] = i; // delete all characters of str1
} else if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // characters match, no operation
} else {
dp[i][j] = 1 + min({dp[i - 1][j - 1], // replace
dp[i - 1][j], // delete
dp[i][j - 1]}); // insert
}
}
}
return dp[m][n];
}
};
class Solution {
public int minOperations(String str1, String str2) {
int m = str1.length(), n = str2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}
}def min_operations(str1, str2):
m, n = len(str1), len(str2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]function minOperations(str1, str2) {
const m = str1.length;
const n = str2.length;
const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i === 0) {
dp[i][j] = j;
} else if (j === 0) {
dp[i][j] = i;
} else if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.