I thought the same but realized you can retrospectively 'insert' the king positions into the position sequence, shifting the remaining sequence one square along for each king, so no more bits required though the data structure is unwieldy!

Only half of the squares are empty, you can almost make a chechboard pattern with the pieces. I don't expect an easy small worst case.