FastPrepFastPrep
Problem Brief

Min Cost to Remove Subsequence (Minimal Cost To Strengthen Password :)

FULLTIMEOA

Team of developers at Amazon is working on a feature that checks the strength of a password as it is set by a user.

Analysts found that people use their personal information in passwords, which is insecure. The feature searches for the presence of a reference string as a subsequence of any permutation of the password. If any permutation contains the reference string as a subsequence, then the feature determines the minimum cost to remove characters from password so that no permutation contains the string reference as a subsequence.

The removal of any character has a cost given in an array, cost, with 26 elements that represent the cost to replace 'a' (cost[0]) through 'z' (cost[25]). Given two strings password and reference, determine the minimum total cost to remove characters from password so that no permutation contains the string reference as a subsequence.

Given the following:

  • A string pwd, representing the password
  • An array of 26 integers removalCosts, denoting the expense to remove each character
  • A string target, the sequence that must not appear as a subsequence in any arrangement of pwd

    • They want you to write a function that computes the minimum total cost necessary to modify the password by deleting characters, ensuring that no permutation of the altered password contains the target as a subsequence.

    Notes:

  • A permutation is a sequence of integers from 1 to n of length n containing each number exactly once, for example, [1, 3, 2] is a permutation while [1, 2, 1] is not.
  • A subsequence is a sequence that can be derived from another sequence by deleting some or no elements, without changing the order of the remaining elements. For example, given the string "abcde", the following are subsequences: "a", "ace", "be", "bde" etc. while sequences like "dea", "abcde" are not subsequences.

    • 1Example 1

    Input
    pwd = "abcdcbcb", target = "bcb", removalCosts = [2, 3, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,0,0,0]
    Output
    3
    Explanation
    :)

    2Example 2

    Input
    pwd = "kkkk", target = "k", removalCosts = [5,1,1,2,4,7,3,4,5,7,5,6,2,1,5,12,5,1,5,0,5,6,4,7,8,50]
    Output
    20
    Explanation
    remove 5 occurances of k at a cost of 5*4 =20

    3Example 3

    Input
    pwd = "adefgh", target = "hf", removalCosts = [1, 0, 0, 2, 4, 4, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    Output
    1
    Explanation
    Example 3 illustration

    4Example 4

    Input
    pwd = "abcdcbcb", target = "bcb", removalCosts = [2, 3, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    Output
    3
    Explanation
    Example 4 illustration
    The count of zeros differs between the two sources. The first source mentions 26 zeros, while the screenshot here shows 22 zeros. I'll go with the count from the official source. Different sources might have some discrepancies. Some we can verify, but others are hard to confirm. So, we’ll go with whatever is closest to the official data. If you know something more accurate, feel free to let us know — really appreciate it!

    Constraints

    Limits and guarantees your solution can rely on.

  • 1 ≤ |pwd| ≤ 10^5
  • 1 ≤ |target| ≤ 10^5
  • 0 ≤ removalCosts[i] ≤ 10° (this is confused, will modify once find reliable source) for i in range [0, 251 --> to be "251" or "25]" is a question; Will modify once find more reliable source :).
  • The strings pwd and target consist of lowercase English letters only.
    • public long minCost(String pwd, String target, int[] removalCosts) {
  // write your code here
}
    Input

    pwd

    "abcdcbcb"

    target

    "bcb"

    removalCosts

    [2, 3, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,0,0,0]

    Output

    3

    Sign in to submit your solution.