How about this? Fix your favourite irrational number $\phi$. I like the golden mean. Let $x_s=[ s\phi ] - [(s-1)\phi]$ ($[t]$ means the integer part of $t$). These sequences are called Sturmian sequences.
Of course $x_s$ is 1 if and only if $s\phi \bmod 1$ lies in $[0,\phi)$.
Now for any $a$ and $k$, you're asking whether $(a+jk)\phi\bmod 1$ lies in $[0,\phi)$ for all $0\le j < n$ or lies in $[\phi,1)$ for all $0\le j < n$.
Provided $S_{k,n}:=\lbrace jk\phi\bmod 1\colon 0\le j < n\rbrace$ is $\delta$-dense in the circle, where $\delta=\min(\phi,1-\phi)$ this cannot happen.
This means you can "compute" the maximum length as a function of $k$, namely $L_{max}(k)=\max\lbrace n\colon S_{k,n}$ is not $\delta$-dense$\rbrace$. In the case of golden mean, $L_{max}(k)$ grows linearly in $k$, but I can't write down the proof of that here (the margin is too small).