Metoda substring() jest faktycznie dość prostym rozwiązaniem, jednak jej wadą jest, że od wyjścia Javy 7 złożoność czasowa substring'a to O(n), ponieważ po każdym usunięciu znaku, tak na prawdę nie obcina go, tylko tworzy sobie nowego stringa, który nie ma tego jednego znaku i podmienia referencje. Żeby to troszkę zoptymalizować mógłbyś zaproponować własną implementację potrzebnej struktury - na przykład tablicę char[], z dodatkową zmienną int index, która by się inkrementowała / dekrementowała w zależności czy wpisujesz, czy usuwasz dany znak. Takie rozwiązanie działałoby w czasie stałym.
Pozdrawiam,