Length of a Growing Word

Hard

You are given a word word of lowercase English letters, a number of rounds rounds, and an array spans of 26 numbers, one for each letter from a to z. In one round, every letter of the word is replaced at the same time by the spans[i] letters that follow it in the alphabet (i is the letter's position, with a at 0). The alphabet wraps around, so a comes again after z. For example, if the span of x is 4, then x becomes yzab. Return the length of the word after exactly rounds rounds. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

word='az', rounds=2, spans=[2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3] → 6

After the first round a turns into bc and z into abc, giving bcabc. In the second round each b and c yields one letter and a yields two: cd + bc + cd = cdbccd, length 6.

Example 2

word='m', rounds=3, spans=[25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25] → 15625

Every letter becomes 25 letters per round, so after three rounds the length is 25³ = 15625.

Example 3

word='hello', rounds=1, spans=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] → 5

Constraints

1 ≤ len(word) ≤ 10⁵
word consists of lowercase English letters only
1 ≤ rounds ≤ 10⁹
len(spans) = 26
1 ≤ spans[i] ≤ 25

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table Math String Dynamic Programming Counting