FastPrepFastPrep
Problem Brief

String Search (Also for Core/Database Engineering)

INTERNOA
See Snowflake online assessment and hiring insights

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 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 🌸࿐ ΰΏ”*:ο½₯ﾟ

    1Example 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.

    2Example 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

    Limits and guarantees your solution can rely on.

  • 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.
    • public int getMaximumRemovals(int[] order, String source, String target) {
  // write your code here
}
    Input

    order

    [7, 1, 2, 5, 4, 3, 6]

    source

    "abbabaa"

    target

    "bb"

    Output

    3

    Sign in to submit your solution.