This paper presents a novel approach to address the constrained coding challenge of generating \emph{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 \emph{$\boldsymbol{\varepsilon(n)}$-almost balanced} if its Hamming weight is between $\boldsymbol{0.5n\pm \varepsilon(n)}$. It is known that for any algorithm with a constant number of bits, $\boldsymbol{\varepsilon(n)}$ has to be in the order of $\boldsymbol{\Theta(\sqrt{n})}$, with $\boldsymbol{\cO(n)}$ average time complexity. However, prior solutions with a single redundancy bit required $\boldsymbol{\varepsilon(n)}$ to be a linear shift from $\boldsymbol{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 \emph{optimal} balanced order of $\boldsymbol{\Theta(\sqrt{n})}$. Additionally, we extend our method to the non-binary case, considering $\boldsymbol{q}$-ary almost polarity-balanced sequences for even $q$, and almost symbol-balanced for $\boldsymbol{q=4}$. Our work marks the first asymptotically optimal solutions for almost-balanced sequences, for both, binary and non-binary alphabet.