I would like to construct a set $S\subseteq\{0,1\}^{2n}$ that satisfy the property:
$$\forall x\neq y\in S\ \ \exists k\in [n]:\forall i,j\in[n], \sum_{t=k+i}^{2n}x_t\neq\sum_{t=k+j}^{2n}y_t$$
In other words, for every two vectors in $S$, there exists $k\in\{0,1,\ldots,n\}$ such that if we delete the first $k$ bits of $x,y$, we can't get the same number of $1$'s in both, after deleting some additional $i,j\in\{0,\ldots,n\}$ bits accordingly.
The motivation for the problem comes from a showing lower bound for a streaming problem in which the answer may rely on approximate sliding window whose size can vary between $n$ and $2n$.
A simple construction for such $S$ is $$\{0^{n+b}1^{n-b}\mid b\in[n]\},$$
As every two words $0^{n+q}1^{n-q}$,$0^{n+a}1^{n-a}$ satisfy the condition for $k=0$.
This gives a lower bound on the size of such $S$ of $n+1$.
If I am not mistaken (didn't get to fully prove it yet), my algorithm implies an upper bound of $O(n^2)$.
What is the maximal size of a set $S$ that satisfies the above property?
