Best-Scoring Stretch of Text

Medium

You are given a string text. Every lowercase English letter is worth something: by default its position in the alphabet (a is worth 1, b is worth 2, …, z is worth 26). Letters listed in the string letters get a different price, though: the letter letters[i] is worth scores[i] (which may be negative). The value of a piece of text is the sum of its letters' values; an empty piece is worth 0. Find the largest value among all contiguous pieces of text, the empty one included.

Example 1

text="hello", letters="l", scores=[-3] → 22

The letters are worth 8, 5, −3, −3 and 15. The whole word gives 8 + 5 − 3 − 3 + 15 = 22, better than any shorter piece.

Example 2

text="cab", letters="abc", scores=[-1, -2, -3] → 0

Every letter is negative, so the best choice is the empty piece, worth 0.

Constraints

1 ≤ len(text) ≤ 10⁵
text and letters consist of lowercase English letters
1 ≤ len(letters) ≤ 26, all letters in letters are distinct
len(scores) = len(letters)
-1000 ≤ scores[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String Dynamic Programming

Similar problems

Split Into Dictionary Words Medium Words Hidden in a Text Medium Word Growth Chain Medium Fewest Stray Letters Medium Erasable Marked Letters Medium

Input

text="hello", letters="l", scores=[-3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.