Fewest deletions to match: hints, no solution
Medium · 2-D dynamic programming
You have two strings a and b made of lowercase letters. In one step you delete a single character from either string. Return the fewest steps needed to make the two strings identical. The resulting string may be empty, so two strings with no letters in common need every character deleted. Deleting keeps the remaining characters in their original order.
Examples
- Input
- a = "sheet", b = "seat"
- Output
- 3
- Note
- Delete h and e from sheet and a from seat to reach set.
- Input
- a = "abc", b = "xyz"
- Output
- 6
- Note
- Nothing is shared, so every character goes.
- Input
- a = "same", b = "same"
- Output
- 0
Constraints
- 0 <= a.length, b.length <= 2000
- Both strings contain only lowercase letters a to z
Hint 1: a nudge
Whatever survives in the two strings has to be the same text. What must be true about how it sits inside each original string?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.