All problems

Melody Matching Stretch

Medium · dynamic programming

Two musicians each play a tune from memory, and the tunes are written down as strings of lowercase letters, one letter per note: first and second.

To see how well the tunes agree, you choose one run of consecutive notes from each tune (a run may be empty) and line the two runs up from left to right. Every note in either run is then either paired with a note of the other run, or skipped. Pairs keep their order: if note p of the first run is paired with note q of the second, every later note of the first run can only pair with a note after q.

The runs score like this:

• a pair of equal notes adds hit,
• a pair of different notes subtracts miss,
• every skipped note subtracts skip.

Return the highest score you can get over every choice of runs and every way of pairing them. Choosing two empty runs scores 0, so the answer is never negative.

Examples

Example 1

Input: first = "abcde", second = "xbcdy", hit = 3, miss = 2, skip = 1

Output: 9

Take the runs "bcd" and "bcd" and pair them note by note: 3 + 3 + 3 = 9. Stretching further to the ends would pair a with x and e with y, which only costs points.

Example 2

Input: first = "abxcd", second = "abcd", hit = 3, miss = 2, skip = 2

Output: 10

Use both whole tunes. Pair a, b, c and d for 12 points and skip the x for -2, which gives 10.

Example 3

Input: first = "cat", second = "dog", hit = 2, miss = 1, skip = 1

Output: 0

No note appears in both tunes, so any pairing loses points. Two empty runs score 0.

Constraints

• 1 <= len(first), len(second) <= 300
• first and second contain only lowercase letters
• 1 <= hit <= 20
• 0 <= miss, skip <= 20