What data structure could we use to efficiently perform these removals?

Use a stack to store the characters. Pop one character off the stack at each star. Otherwise, we push the character onto the stack.