How should I practice Find Maximum Score?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Find Maximum Score associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · String

Find Maximum Score

Learn this problem

● HardAmazonNEW GRADOA

See Amazon hiring insights

Problem statement

Data analysts at Amazon are analyzing a string, data. Each of its characters is worth 1 point.

Any substring in which every pair of adjacent characters differs by at most one position in the English alphabet is also worth 1 point. For example, "aa", "ab", and "ba" are each worth 1 point.

To improve the score, at most one character may be replaced with any other lowercase English letter.

Given the string data, find the maximum score that can be achieved.

Function

findMaximumScore(data: String) → int

Examples

Example 1

data = "aabacfgh"return = 21

The initial score is 17: one point for each of the 8 letters, plus the following 9 substrings contributing one point each: 'aa', 'ab', 'ba', 'aab', 'aba', 'aaba', 'fg', 'gh', 'fgh'. In the optimal scenario, change the character at index 4 (data[4] = 'c') to 'b'. The string becomes "aababfgh" and the score is calculated as: 1 point for each of the 8 letters of the string. The following substrings are worth 1 point each: data[0:1] = "aa", data[0:2] = "aab", data[0:3] = "aaba", data[0:4] = "aabab". Total count = 4. data[1:2] = "ab", data[1:3] = "aba", data[1:4] = "abab". Total count = 3. data[2:3] = "ba", data[2:4] = "bab". Total count = 2. data[3:4] = "ab". Total count = 1. data[5:6] = "fg", data[5:7] = "fgh". Total count = 2. data[6:7] = "gh". Total count = 1. Therefore, the total is 8 + 4 + 3 + 2 + 1 + 2 + 1 = 21. Hence, the answer is 21.

Example 2

data = "abcb"return = 10

The string "abcb" is already in one of its most efficient forms, so no change can increase its score. 1 point for each of the 4 letters: 'a', 'b', 'c', 'b'. Total = 4. The following substrings are worth 1 point each: "ab", "bc", "cb", "abc", "bcb", "abcb". Total = 6. Therefore, the total is 4 + 6 = 10. Hence, the answer is 10.

Example 3

data = "abez"return = 7

Change "abez" to "abaz". Each of the resulting scoring substrings is worth 1 point. Hence, the final answer is 7.

Constraints

data consists only of lowercase English letters ('a' to 'z').
At most one character of data may be replaced, and the replacement must be a lowercase English letter.
A substring scores 1 point only if every pair of adjacent characters in it differs by at most one position in the alphabet.