FastPrep
Problem · Binary Search

String Search (Also for Core/Database Engineering)

Learn this problem
● MediumSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

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 ith 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

    getMaximumRemovals(order: int[], source: String, target: String) → int

    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 🌸࿐ ࿔*:･ﾟ

    Examples

    Example 1

    order = [7, 1, 2, 5, 4, 3, 6]source = "abbabaa"target = "bb"return = 3
    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

    order = [1, 4, 2, 3, 5]source = "hkbdi"target = "kd"return = 1
    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.

    • More Snowflake problems

    drafts saved locally
    public int getMaximumRemovals(int[] order, String source, String target) {
  // write your code here
}
    order[7, 1, 2, 5, 4, 3, 6]
    source"abbabaa"
    target"bb"
    expected3
    checking account