Consider a string of characters $a, b, c$ only. Such a string is called good if the number of $a$'s + number of $b$'s is equal to the number of $c$'s.
Given an integer $n$, find the number of strings of length $n$ consisting only of characters $ a,b,c$ such that all of its substrings of length $k$ are good.
Example:
$ n = 3 ,k = 2 $ is $6$,
$ n = 2,k = 1 $ is $0$
I could only solve when there are only two characters but can anyone help me how to solve when there are three characters.
For a good string $s$ of length $k$, let $M(n,s)$ denote the number of strings of length $n$ terminating in $s$ in which every $k$-letter substring is good. The quantity $M(n,s)$ is given by the following recurrence: $$ \begin{align} &M(k,s) = 1 \\ &M(n+1,ta) = M(n+1,tb) = M(n,at) + M(n,bt) \\ &M(n+1,tc) = M(n,ct) \end{align} $$ Here $t$ is a string of length $k-1$. Summing over all good strings $s$, we can solve your problem.
Since $a$ and $b$ are really interchangeable, we can also consider a slightly different recurrence, in which $s$ only consists of $a$'s and $c$'s: $$ \begin{align*} &M'(k,s) = 2^{\#_a(s)} \\ &M'(n+1,ta) = 2M'(n,at) \\ &M'(n+1,tc) = M'(n,ct) \end{align*} $$ Here the second parameter is a "template" in which $a$ stands for either $a$ or $b$.
Using either recurrence, you can find explicit formulas for any given value of $k$.
