FastPrep
Problem · Dynamic Programming

Min Cost to Remove Subsequence

Learn this problem
● HardAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

A 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 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.

Function

minCost(password: String, reference: String, cost: int[]) → long

Complete the function minCost in the editor below.

minCost has the following parameters:

  • string password: the password string
  • string reference: the string which should not exist as a subsequence in any permutation of password
  • int cost[26]: the costs to remove each character in the lowercase English alphabet

Returns

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

Input Format For Custom Testing

The first line contains a string, password.

The next line contains a string, reference.

The next line should contain a constant integer 26, denoting the next 26 lines describe the array cost.

Each of the next 26 lines contains an integer, cost[i].

Examples

Example 1

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]return = 1

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'

↓
a
d
e
f
g

Cost of removal = 1

Case 2

Cost
1
2
4
4
3
1
Character
a
d
e
f
g
h

Remove letter 'f'

↓
a
d
e
g
h

Cost of removal = 4

  • 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.

Note: This example was added on June 26, 2026, backed by the official source found. 🐣

Example 2

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]return = 3

An optimal move is to remove the occurrences of the letter 'c' resulting in a modified password = "abdbb". The total cost of removal = 1*3 = 3.

Note: This example was added on June 26, 2026, backed by the official source found. 🐥

Example 3

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]return = 20

Remove 5 occurrences of 'k' at a cost of 5*4 = 20.

Source note: The official screenshot says 5 occurrences, while password = "kkkk" has 4 occurrences of 'k'. I kept the screenshot wording above, and the shown calculation 5*4 = 20 matches the example output. If you spot anything that looks off, please tell me and we can look at the best way to fix it together. 🐿️

Note: This example was added on June 26, 2026, backed by the official source found. 🐢

Constraints

  • 1 ≤ |password| ≤ 10^5
  • 1 ≤ |reference| ≤ 10^5
  • 0 ≤ cost[i] ≤ 10^9 for i in range [0, 25]
  • The strings password and reference consist of lowercase English letters only.

Note: These constraints were added on June 26, 2026, backed by the official source found. 🐼

More Amazon problems

drafts saved locally
public long minCost(String password, String reference, int[] cost) {
  // write your code here
}
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]
expected1
checking account