# Counting strings with balanced substrings

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$$.