PROBLEM LINK:Author: Vitaliy Herasymiv DIFFICULTY:EasyMedium. 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 $ni$ 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, i1)\times \text{V}(AS, \min(m, \text{len}(AS)) + f(BS, n, i1)\times \text{V}(BS, \min(m, \text{len}(BS))$ because the ith index can be CZ, in which case we are left with string of length $i$ (index $0$ to $i1$) 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+m1, n) is valid or not thats why the term $f(AS, n, i1)\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} , i1, i1)$. 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
This question is marked "community wiki".
asked 21 Mar '15, 01:37

What is the mistake in this method? Let dp[N] be the number of valid strings of length N, and X be the number of hated strings(of length M each). If N < M, dp[N] = 26 ^ N, Else, dp[N] = 26 * dp[N1]  X * dp[NM]. Will there be some cases that will not be counted? (or counted more than once?) answered 25 Mar '15, 15:18

Edit: It is fixed now Thanks .. :D The tutorial is not readable. Please edit it.
answered 23 Mar '15, 00:59

Can anyone check my logic please. my logic is 1. count the number of forbidden words(X<S<Y) (=c)[using binary format...A=0,B=1] 2. find all the words that have these words as substring (=w)[normal combinatorics] 3. subtract it from 26^n(26^nc*w) answered 25 Mar '15, 13:28

I must praise you for such a neat, precise and awesome editorial.Thanks brother :) answered 06 Apr '15, 20:13

can someone explain me what this does ? answered 17 May '15, 11:48
