Si el rendimiento es importante, considera usar "Ropes" en vez de Strings

Los Ropes son una representación alternativa para las cadenas de caracteres. Habitualmente, una cadena de caracteres es representada internamente por un array de tamaño fijo. Desde hace bastante tiempo, se conocen estructuras para representar cadenas de caracteres que presenta mucho mejor rendimiento para operaciones como concatenación o reemplazado de caracteres. Ambas operaciones, si se representa la cadena de caracteres con un array, tienen una complejidad (en el mejor de los casos) lineal.

Sin embargo, representando la cadena de caracteres mediante un árbol es posible efectuar ambas operaciones en un tiempo logarítmico. En esto es, precisamente, en lo que consisten los "Ropes". No es una idea nueva en absoluto (podéis leer sobre los Ropes en este artículo de 1995).

Lo que sí es bastante reciente es que Amin Ahmad ha publicado en su web una implementación 100% Java de Ropes. Esta implementación tiene una complejidad logaritmica respecto al tamaño de la cadena de caracteres en operaciones de concatenar, borrar, reemplazar e insertar; complejidad muy inferior tanto a la de String (que puede llegar a ser cuadrática en algunos casos) y a la de StringBuffer (lineal).

Eso sí, un Rope, al representarse mediante un árbol, va a consumir más memoria que un String de toda la vida. De todos modos, si tu problema en la CPU y no la memoria, no estaría de más echarle un vistazo. La implementación de Ropes se distribuye bajo licencia GPL.