### PROBLEM LINK:

Author: Vitaliy Herasymiv

Tester: Istvan Nagy

Editorialist: Amit Pandey

### DIFFICULTY:

Easy-Medium.

### PREREQUISITES:

Counting, Dynamic Programming, Recursion.

### PROBLEM:

Given strings X and Y, count the number of strings of length n which do not contain string S (X \leq S \leq Y) of length m(\leq n) as a substring.

### EXPLANATION:

In this problem it is asked to count the number of strings of length n which do not contain string S (X \leq S \leq Y) of length m(\leq n) as a substring. Let H be a set of strings which are lexicographically in between X and Y inclusively that is H = \{S : |S| = m \wedge X\leq S \leq Y \}. Now define \text{dp}[i] as the number of strings of length exactly equal to i which do not contain string(s) which belong(s) to H as a substring. It is clear that if i < m then \text{dp}[i] = 26^i.

For i \geq m, define a recursive function f(S, n, i) which takes input string s, ending index n and index i which is to be filled. This function returns the number of valid strings( which are not hated ) whose last n-i letter are already fixed as S. For example f(AB, 5, 3) will return number of valid strings of length 6(assuming zero indexing and n=5) whose last 2 letters are fixed as “AB”. Also define a function V(S, len) which return 1 if string S of length len is valid else it returns 0. Note that if len < m then the string is trivially valid else we have to check X \leq S \leq Y. Further len will always be less than or equal to m by virtue of following definition of f(S, n, i) where a value greater than m is never passed to V(S, len)

Now f(S, n, i) = 24\text{dp}[i] + f(AS, n, i-1)\times \text{V}(AS, \min(m, \text{len}(AS)) + f(BS, n, i-1)\times \text{V}(BS, \min(m, \text{len}(BS)) because the ith index can be C-Z, in which case we are left with string of length i (index 0 to i-1) thats why the term 24\text{dp}[i]; or ith index can be ‘A’ in that case we have to check whether the string from ith index to min(i+m-1, n) is valid or not thats why the term f(AS, n, i-1)\times \text{V}(AS, \min(m, \text{len}(AS)) and similar expression when ith index is ‘B’. Base case will be when i=-1 in that case return 1.

Now, for i \geq m, \text{dp}[i] = f(\text{empty string} , i-1, i-1). So, the final answer to the question will be \text{dp}[n]. Refer to the editorialist code in the solution section for more detail. The worst case time complexity of this algorithm is \mathcal{O}(n 2^n).

### Solution:

Setter’s solution can be found here

Tester’s solution can be found here

Editorialist’s solution can be found here