Можно взглянуть, как я сделал
тут.
Разъяснения:
1.Можно с помощью битовых операций быстро определить, подлежит ли символ замене, особенно если max-min < 64. Пачки символов, которые не подлежат, дописываем одним куском.
2. Сами символы можно разделить на три группы: заменяемые на "", заменяемые на одну букву и заменяемые на две. Вторые сложить в массив чаров, третьи — в массив строк. Обрабатывать отдельно.