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).
*Some more stuff as requested by OP*
Claim: If $d(k\phi,\mathbb Z/6)=\epsilon$ then $L_{max}(k)<1/\epsilon$.
Proof: Let $k\phi=a/6+\epsilon$, where $|\epsilon|<1/12$. Notice that $\delta<1/3$. If $a=0$, then $1/\epsilon$ steps produces an $\epsilon$-dense subset of the circle. If $a=1$ or 5, then 12 steps produces a $\delta$-dense subset of the circle. If $a=3$, then $1/\epsilon$ steps produces a $2\epsilon$-dense subset of the circle [because $2k\phi$ is $2\epsilon$-close to $\mathbb Z$] and if $a=2$ or 4, then $1/\epsilon$ steps produces a $3\epsilon$-dense subset of the circle.
Next notice $d(k\phi,\mathbb Z/6)\le d(6k\phi,\mathbb Z)$. From Hardy and Wright (5th ed, Theorem 194) plus a simple argument you get $d(k\phi,\mathbb Z)\le 1/(Ak)$ for a suitable $A$.
Combining these ingredients gives the linear growth of $L_{max}$.