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.

Say we don't want to allocate memory dynamically though. We just want to allocate O(W) bits at the start of the program. Can you still do it?