Interview Questions/Coding/Make It A Subsequence

Make It A Subsequence

Preview mode. Log in to edit, run, submit, and save progress.

Medium

Make It A Subsequence

You are given two case-sensitive strings: firstString and secondString. You may remove characters from secondString. The remaining characters must stay in their original order. Your goal is to make the remaining secondString a subsequence of firstString. If you remove no characters, the cost is 0. Otherwise, suppose the removed characters originally had indices from L to R in secondString. The cost is: R - L + 1 Return the minimum possible cost. Since removing extra characters between L and R never increases the cost, the task can be viewed as removing one contiguous window from secondString so that the remaining prefix and suffix together form a subsequence of firstString.

Examples

Example 1
Input:
abcde
ace
Output:
0

Explanation: "ace" is already a subsequence of "abcde".

Approach hint

If the first and last removed characters are known, removing everything between them does not increase the cost.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp