FastPrep

Description

Solutions

Min Cost to Remove Subsequence

🔥 FULLTIME📚RELATED PROBLEMS

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.

Note:

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 elements, without changing the order of the remaining elements. For example, given the string "abcde", the following are subsequences: "a", "ace", "bde", "bde" etc. while sequences like "dea", "acbde" are not subsequences.

Function Description

Complete the function minCost in the editor.

minCost has the following parameters:

1. String password: the password string
2. String reference: the string which should not exist as a subsequence in any permutation of password
3. int cost(26): the costs to remove each character in the lowercase English alphabet

Returns

long integer: the minimum cost to remove characters from password such that no permutation contains the reference string as a subsequence

Example 1:

Input:  password = "abcdcbcb", reference = "bcb", cost = [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:
:)

Example 2:

Input:  password = "kkkk", reference = "k", cost = [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

Example 3:

Input:  password = "adefgh", reference = "hf", cost = [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:


Some possible removals from password so that no permutation contains the string reference as a subsequence are:


Case 1:
cost: 1 2 4 4 3 1
character: a d e f g h


remove letter h would result in below and cost of removal = 1


a d e f g


Case 2:
cost: 1 2 4 4 3 1
character: a d e f g h


remove letter f would result in and cost of removal = 4


a d e g h


In Case 1 we are removing only a single letter 'h' so the cost of removal in this case becomes 1.


Similarly in Case 2 we are removing only a single letter 'f' so the cost of removal in this case becomes 4


Since removing either h or f will remove the existence of reference as a subsequence so we optimally choose to remove 'h' (Case 1), therefore the minimum cost is 1.

Example 4:

Input:  password = "abcdcbcb", reference = "bcb", cost = [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:


An optimal move is to remove the occurrences of the letter 'c' resulting in a modified password = "abdbb".

The total cost of removal is = 1*3 = 3

Constraints:

1 ≤ /password / ≤ 10⁵

1 ≤ /reference / ≤ 10⁵

0 ≤ cost[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 password and reference consist of lowercase English letters only.