The bit stuffing algorithm is a technique for coding constrained sequences by the insertion of bits into an arbitrary data sequence. This approach was previously introduced and applied to (d, k) con- strained codes. Results show that the maximum av- erage rate of the bit stuffing code achieves capacity when k = d +1 or k = ∞, while it is suboptimal for all other (d, k) pairs. We propose a modification to the bit stuffing algorithm. We show analytically that the proposed algorithm achieves improved average rates over bit stuffing for most (d, k) constraints.