FastPrep
Problem · Dynamic Programming

Calculate Efficiency Score

Learn this problem
● HardAmazon logoAmazonOA
See Amazon hiring insights

Problem statement

You are given an initial parentheses sequence represented by the string s, along with a Parentheses Perfection Kit containing different types of parentheses in the form of the string kitParentheses and their respective efficiency ratings in the efficiencyRatings array (both of size m). The EfficiencyScore of the original string s is initially 0. You can use any number of unused parentheses from the kit to create the final sequence, as long as the final sequence remains balanced.

The task is to determine the maximum possible EfficiencyScore that can be achieved for the resulting balanced sequence. Note: It is guaranteed that the sequence can be made balanced by adding zero or more parentheses from the kit.

Function

calculateEfficiencyScore(s: String, kitParentheses: String, efficiencyRatings: int[]) → long

Examples

Example 1

s = ")(("kitParentheses = ")(()))"efficiencyRatings = [3, 4, 2, -4, -1, -3]return = 6

The initial sequence starts with an unmatched closing parenthesis, so at least one opening parenthesis must be inserted before it. It also has one more opening than closing parenthesis overall. Choose the opening parenthesis rated 4 and the closing parentheses rated 3 and -1. These insertions can form a balanced sequence and contribute an efficiency score of 4 + 3 - 1 = 6, which is maximal.

Constraints

  • 1 ≤ |s| < 2 * 105
  • 0 ≤ m < 2 * 105
  • -109 ≤ efficiencyRatings[i] ≤ 109
  • Both strings s and kitParentheses consist of opening and closing parentheses only

    • More Amazon problems

    drafts saved locally
    public long calculateEfficiencyScore(String s, String kitParentheses, int[] efficiencyRatings) {
  // write your code here
}
    s")(("
    kitParentheses")(()))"
    efficiencyRatings[3, 4, 2, -4, -1, -3]
    expected6
    checking account