Hard Python Practice (Codility Task 2) | Dataford Interview Questions

Rakuten Payment validates compact symbol sequences generated by payment-processing components. Given a string length, alphabet size, pattern, and target occurrence count, compute how many strings contain the pattern exactly k times.

Occurrences may overlap. For example, "aaa" contains "aa" twice, at positions 0 and 1.

Return the count modulo mod.

Formal Specification

Implement count_strings(n, alphabet_size, pattern, k, mod):

n is the required string length.
The alphabet consists of the first alphabet_size lowercase English letters: a, b, ..., starting from a.
pattern is a non-empty lowercase string using only characters in that alphabet.
Count strings of length exactly n whose number of occurrences of pattern is exactly k.
Return an integer in [0, mod - 1].

Use an efficient algorithm. Enumerating all alphabet_size ** n strings is infeasible.

Constraints

1 <= n <= 5000
1 <= alphabet_size <= 26
1 <= len(pattern) <= 50
0 <= k <= 50
pattern uses only the first alphabet_size lowercase letters
10^7 <= mod <= 10^9 + 7

Function Signature

def count_strings(n, alphabet_size, pattern, k, mod):

Your question is Hard Python Practice (Codility Task 2). Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem