  This paper presents a novel approach to address the constrained coding
challenge of generating almost-balanced sequences. While strictly balanced
sequences have been well studied in the past, the problem of designing
efficient algorithms with small redundancy, preferably constant or even a
single bit, for almost balanced sequences has remained unsolved. A sequence is
$\varepsilon(n)$-almost balanced if its Hamming weight is between $0.5n\pm
\varepsilon(n)$. It is known that for any algorithm with a constant number of
bits, $\varepsilon(n)$ has to be in the order of $\Theta(\sqrt{n})$, with
$O(n)$ average time complexity. However, prior solutions with a single
redundancy bit required $\varepsilon(n)$ to be a linear shift from $n/2$.
Employing an iterative method and arithmetic coding, our emphasis lies in
constructing almost balanced codes with a single redundancy bit. Notably, our
method surpasses previous approaches by achieving the optimal balanced order of
$\Theta(\sqrt{n})$. Additionally, we extend our method to the non-binary case
considering $q$-ary almost polarity-balanced sequences for even $q$, and almost
symbol-balanced for $q=4$. Our work marks the first asymptotically optimal
solutions for almost-balanced sequences, for both, binary and non-binary
alphabet.
