How many restricted length strings are there without significant repetitions
For each particular $c,N,M$, this can be solved explicitly by constructing a DFA accepting the language. The general case may also be approached heuristically, though the dependency structure makes heuristic estimates harder to make.

The case $N = 1$ can be solved explicitly. Suppose that the alphabet is $\{0,\ldots,c-1\}$. Represent each word $w_1\ldots w_n$ as the sequence of differences $x_1\ldots x_n$, where $x_1 = w_1$ and $x_i = w_i - w_{i-1} \pmod{c}$ for $i &gt; 1$. Your language then becomes
$$
\epsilon + \{0,\ldots,c-1\}((\epsilon + 0 + \cdots + 0^{M-1})\{1,\ldots,c-1\})^*(\epsilon + 0 + \cdots + 0^{M-1}).
$$
The corresponding generating function is
$$
1 + cx \cdot \frac{1}{1-\frac{x^M-1}{x-1}\cdot(c-1)x} \cdot \frac{x^M-1}{x-1} =
\frac{x^{M+1}-1}{cx-1-(c-1)x^{M+1}}.
$$
The asymptotic growth of the number of words is controlled by the smallest (in modulus) root of $(c-1)x^{M+1}-cx+1$. If this modulus is $\alpha$, then the growth rate of the sequence (under reasonable assumptions) is $\Theta((1/\alpha)^n)$.

Plotting a few of the polynomials $(c-1)x^{M+1}-cx+1$ reveals that there are two real roots in $[0,1]$. We are interested in the one near $1/c$. Suppose that $x=(1+\epsilon)/c$ is a root. Then
$$
1 = cx - (c-1)x^{M+1} = 1+\epsilon - \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1},
$$
and so
$$
\epsilon = \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}.
$$
This shows that $\epsilon$ is exponentially small in terms of $M$, and so we can approximate $(1+\epsilon)^{M+1}$ by $1+(M+1)\epsilon$ to obtain the equation
$$
\epsilon \approx \frac{c-1}{c^{M+1}}(1 + (M+1)\epsilon)
$$
whose solution is
$$
\epsilon \approx \frac{\frac{c-1}{c^{M+1}}}{1-(M+1)\frac{c-1}{c^{M+1}}} = \frac{c-1}{c^{M+1}-(c-1)(M+1)} \approx \frac{c-1}{c^{M+1}}.
$$
Since $1/x = c/(1+\epsilon) \approx (1-\epsilon) c$, altogether we obtain that the number of words of length $n$ in which no symbol repeats $M$ times is $\Theta(\alpha^n)$, where
$$ \alpha \approx c - \frac{c-1}{c^M}. $$

Carrying this sort of analysis for $N &gt; 1$ seems significantly more difficult.