In that case the complexity becomes O(N * A) where A is the size of the alphabet, since at every step you have to go through the whole bitset in order to count

In that case the complexity becomes O(N * A) where A is the size of the alphabet, since at every step you have to go through the whole bitset in order to count how many bits are set. Edit - actually it should be possible to update the count incrementally, so it should still be O(N) I think.