comunque sbagli anche nel non assegnare il risultato del replace
str=str.replace(lettere[i], sostituzioni[i]);

poi, se nel replace non usi una regExp vai a sostituire solo la prima occorrenza
che probabilmente non e' cio' che vuoi