Para hacer trabajos de sustitución de cadenas en Java es recomendable el uso de las clases Pattern y Matcher, pero sí lo que vas a hacer es algo tan sencillo como lo que expones, la propia clase String proporciona métodos de busqueda y sustitución.

Por ejemplo, sí tu quisieses sustituir una S (tal y como dices), en esta cadena: "aaaSbc" tendrías que hacer esto:

String cadena = new String("aaaSbc"); //Declaración de la cadena
cadena = cadena.replaceFirst("S", "bcd"); //Método que reemplaza la primera ocurrencia

El método replaceFirst tiene como primer parámetro una expresión regular (si no conoces lo que es, busca por Internet porque la verdad es interesante), el segundo parámetro es la cadena que va a sustituir a la ocurrencia.

Existe otro método, replaceAll, que, como su propio nombre indica, reemplaza todas las ocurrencias que hay en la cadena.

De esta forma no tendrías que andar pensando en como realizarlo, ya que la propia clase te ofrece esta funcionalidad. Sí quisieses implementarlo por ti mismo, supongo que no tendría mucha complejidad en los casos más simples.

Saludos y si hay alguna duda, comenta  .

pero si quiero sustituir por todo un arreglo con otro arreglo???

por ejemplo
aabc

[a,a,b,c,f,g]    por [asd,a,r,d]
a sustituir por a
a sustituir por r
b sustituir por d
c sustituir por asd
salida:
ardasdfg