String Search (Also for Core/Database Engineering)

Problem Overview

• Find the maximum number of removals from source, applied in the given permutation order[], such that target still remains a subsequence.
• Inputs: order[] (permutation of 1..n), source string, target string; Output: integer maximum; Constraints: source length up to 1e5, target initially a subsequence.
• Context: models a search engine’s tolerance to deletions when matching similar words.
• Company: Snowflake coding interview problem; a frequent interview question for Core/Database Engineering.