What is the brute force approach and complexity for Delete Operation for Two Strings?

Compare the last letters: keep both on a match, else delete one and recurse with time complexity O(2^(N + M)) and space complexity O(N + M).

What is the optimal approach and complexity for Delete Operation for Two Strings?

Find the longest shared sequence with two rows; the deletions are n + m − 2 · LCS with optimal time complexity O(N · M) and space complexity O(min(N, M)).

Delete Operation for Two Strings

Q: How do you identify the pattern for Delete Operation for Two Strings?

Look for key signals in the prompt: "fewest steps to make them the same" indicates The goal looks like an edit problem, but the letters that stay are what matter, so it is an LCS problem in disguise.; "delete one letter from either string" indicates Deletions can come from both words, so count what each word loses: n − L and m − L..

Medium·LeetCode #583 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given two strings word1 and word2. In one step you can delete one letter from either string. Find the fewest steps needed to make the two strings equal.

Input

Two strings, word1 and word2.

Output

The smallest number of deletions, in total, that makes the two strings equal.

Example 1

Input: word1 = "sea", word2 = "eat"

Output: 2

Delete s from sea to get ea. Delete t from eat to get ea. That is two steps.

Example 2

Input: word1 = "leetcode", word2 = "etco"

Output: 4

Keep etco. Delete the four letters of leetcode that are not used, and nothing from etco.

Constraints

• 1 ≤ word1.length, word2.length ≤ 500
• Lowercase English letters only.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“fewest steps to make them the same”

→ The goal looks like an edit problem, but the letters that stay are what matter, so it is an LCS problem in disguise.

“delete one letter from either string”

→ Deletions can come from both words, so count what each word loses: n − L and m − L.

Approach Complexity Ladder

Brute Force — recursion on the last lettersO(2^(N + M))O(N + M)

Compare the last letters: keep both on a match, else delete one and recurse

Better — a table of deletion countsO(N · M)O(N · M)

dp[i][j] = fewest deletions for each pair of prefixes; each cell is filled once

Optimal — LCS in two rows, then n + m − 2 · LCSO(N · M)O(min(N, M))

Find the longest shared sequence with two rows; the deletions are n + m − 2 · LCS

Brute Force Intuition

Let steps(i, j) be the fewest deletions that make the first i letters of word1 and the first j letters of word2 equal. If the last letters match, keep both and recurse on steps(i−1, j−1). If they differ, delete one of them: 1 + min(steps(i−1, j), steps(i, j−1)). An empty side needs one deletion for each letter of the other side.

Recognition rule for this sub-pattern:

Match → 1 + dp[i−1][j−1]; otherwise max(dp[i−1][j], dp[i][j−1]). Counting versions add the cases instead of taking a max.

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture