FastPrepTrader Joe Trades

Trader Joe Trades

Amazon logoAmazon● HardNEW GRADOA

Updated

Problem statement

Joe the trader works with 26 types of trade operations, labeled with the uppercase letters 'A' to 'Z'. He is given a list of operations in a fixed order. Operation i has type tasks[i] (the i-th character of the string tasks) and earns rewards[i].

Joe goes through the operations in order and either executes or skips each one. The executed operations, kept in their original order, must never contain more than k operations of the same type in a row. For example, if k = 2, the executed sequence "BCCC" is invalid because 'C' appears 3 times in a row, while "BCBCC" is valid.

Skipping an operation does not reset the count of identical operations in a row: only the executed operations form the sequence that is checked.

Return the maximum total reward of the executed operations.

Function

traderTrades(tasks: String, rewards: int[], k: int) → int

Examples

Example 1

tasks = "BAAAB"rewards = [1, 4, 2, 10, 3]k = 2return = 18

The best strategy is to skip the task at index 2 (tasks[2] = 'A'). The sequence then becomes "BAAB", leading to a total gain of 1 + 4 + 10 + 3 = 18.

Constraints

  • 1 ≤ tasks.length ≤ 10^5
  • rewards.length = tasks.length
  • tasks contains only uppercase English letters 'A' to 'Z'.
  • 1 ≤ rewards[i] ≤ 10^4
  • 1 ≤ k ≤ tasks.length

More Amazon interview questions

Similar questions at other companies

Interview reports that mention this question

Amazon interview experiences

See Amazon hiring insights
Saved
class Solution {
    public int traderTrades(String tasks, int[] rewards, int k) {
      // write your code here
    }

}
Checking account…