Let's consider $n$-bit strings $x$. Definitions:
- $f(x,i)$ = bit string $x$ with last $i$ bits complemented.
- $b(x)$ = "imbalance" of $x$: number of 1s in $x$ $-$ number of 0s in $x$.
Now fix a string $x$. Consider the function $g(i) = b(f(x,i))$. Observations:
- $g(0) = b(x)$.
- $g(n) = -g(0)$.
- $|g(i) - g(i+1)| = 2$ for all $i$. We either remove one 0 and add one 1 or vice versa.
Now it follows that there exists an $i$ such that $-1 \le g(i) \le +1$.
Hence we can construct an $(n+O(\log n))$-bit string $y$ as follows: concatenate $f(x,i)$ and the binary encoding of the index $i$. The absolute value of the imbalance of $y$ is $O(\log n)$. Moreover, we can recover $x$ given $y$; the mapping is bijection.
Finally, you can add $O(\log n)$ dummy bits that reduce the imbalance of $y$ from $O(\log n)$ to $0$.