text and pattern. You may delete any characters from pattern so that what remains is a subsequence of text (it can be obtained from text by crossing out characters without reordering the rest).
The cost of the deletion is 0 if nothing is deleted; otherwise let left be the smallest and right the largest index among the deleted characters of pattern, and the cost is right - left + 1. Characters between left and right need not be deleted, but that does not lower the cost, so cutting out a single contiguous piece is just as good.
Return the minimum possible cost.text="planet", pattern="plxnt" → 1
Removing just x (index 2) is enough: "plnt" is a subsequence of "planet". The cost is 2 − 2 + 1 = 1.
text="abc", pattern="cba" → 2
All of "cba" does not fit, and no two of its letters appear in that order. Removing indices 1 and 2 leaves "c", for a cost of 2.
text="banana", pattern="ana" → 0
"ana" is already a subsequence, so nothing needs to go.
len(text), len(pattern) ≤ 10⁵text and pattern consist of lowercase English letterstext="planet", pattern="plxnt"
1
Run checks the first 3 tests in your browser. Submit checks all 132 tests on the server, hidden ones included.