FastPrep

Description

Solutions

String Search (Also for Core/Database Engineering)

🤘 INTERN📚RELATED PROBLEMS

A search engine is being trained on an algorithm for searching similar words. Given two words, source and target, characters are removed from the string source one by one following the sequence of indices defined by the permutation order[]. More formally, order[] is a permutation of length n (length of string source), and in the i^th step of the removal, the character at index order[i] is removed from the string source, while keeping the other characters at their original indices.

The string target is said to be searchable in the string source, if it appears as a subsequence in the source string. Find the maximum number of characters which can be removed by following the order defined by the permutation order[], such that the string target remains searchable in the string source.

Note:

The removals are performed according to the order of permutation.

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not because 2 appears twice in the array; [1, 3, 4] is also not a permutation because n = 3, but 4 appears in the array.

A subsequence of a string is a string which can be formed by deleting some (can be none) of the characters from the original string without disturbing the relative positions of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not.

It is guaranteed that string target exists as a subsequence in the source initially.

Function Description

Complete the function getMaximumRemovals in the editor.

getMaximumRemovals has the following parameters:

int order[order_size]: the order in which characters are removed from string source

string source: the initial string

string target: the desired subsequence

Returns

int: the maximum possible removals such that target exists as a subsequence of source

𓂃🖊, Credit to robot 🌸࿐ ࿔*:･ﾟ

Example 1:

Input:  order = [7, 1, 2, 5, 4, 3, 6], source = "abbabaa", target = "bb"
Output: 3 
Explanation:
      The removals occur as follows (the characters in bold show the desired subsequence, whereas "-" represents removed characters):

      1. Character at index 7 is removed; source = "abbaba-" → "abbaba-". Thus, target exists as a subsequence.
      2. Character at index 1 is removed; source = "-bbaba-" → "-bbaba-". Thus, target exists as a subsequence.
      3. Character at index 2 is removed; source = "--baba-" → "--baba-". Thus, target exists as a subsequence.
      4. Character at index 5 is removed; source = "--ba-a-" → "--ba-a-". Here, target does not exist as a subsequence.

      A maximum of 3 removals can be done.

Example 2:

Input:  order = [1, 4, 2, 3, 5], source = "hkbdi", target = "kd"
Output: 1 
Explanation:
      1. The character at index 1 is removed; source = "-kbdi" → "-kbdi". target exists as a subsequence.
      2. The character at index 4 is removed; source = "-kb-i" → "-kb-i". target does not exist as a subsequence.

Constraints:

1 ≤ |source| ≤ 10^5

1 ≤ |target| ≤ |source|

It is guaranteed that the array order[] forms a permutation.

It is guaranteed that the length of array order[] and string source are equal.

It is guaranteed that string target exists as a subsequence in source initially.