Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same.

Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, 010, 011, 100$)

I am trying to get a recurrent formula of this problem but I don't know how to.

  • $\begingroup$ why (000) and (111) aren't in there? $\endgroup$ – Exodd Sep 28 '14 at 9:18
  • $\begingroup$ Because k consecutive characters must no be the same. In the example, k equal 3. $\endgroup$ – Xeing Sep 28 '14 at 11:07

Let $T(n, k)$ represent the number of strings with k consecutive characters that are the same. We assume that a character can only hold either $0$ or $1$ just by going your example.

$T(n, n) = 2*1$ since there's only one string that has n consecutive characters for each character and we have 2 such characters.

$T(n, n-1)$ includes $T(n,n)$ as the strings counted by the latter already have $n-1$ consecutive identical characters. What remains is for us to find strings that have exactly $n-1$ consecutive characters which is given by $2 * (n - (n-1) + 1)$. Therefore:

$$T(n, n-1) = T(n,n) + 2 * (n- (n-1) + 1)$$

In general, we can count the number of strings with exactly k consecutive identical characters by $2 * (n - k + 1)$ where the $2$ factor comes from the # of characters possible ($0$ or $1$) and the $(n - k + 1)$ factor comes from the possible ways for a character to appear exactly k consecutively.

To find $T(n, k)$, we simply add up the possible strings that has exactly k consecutive identical characters, then the strings that has more than k consecutive exact characters given by $%T(n, k+1)$:

$$T(n, k) = 2 * (n - k + 1) + T(n, k + 1)$$

Therefore, the number of strings that do not have k consecutive identical characters in recurrence form is:

$$2^n - T(n,k) = 2^n - 2*(n-k+1) - T(n, k+1)$$

where $2^n$ is the total number of strings possible of n length and 2 characters.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.