Here's a quick rough one-pass algorithm implemented in C# (I don't know Java).
Things to be altered/improved are the Dictionary (lookup table) and, as written, it requires that the string end with whitespace (left as an exercise).
You would need a different Dictionary for each step.
System.Collections.Generic.Dictionary<string,string> rep =
new System.Collections.Generic.Dictionary<string,string>() ;
rep [ "C" ] = "C#" ;
rep [ "C#" ] = "D" ;
rep [ "D#" ] = "E" ;
rep [ "E" ] = "F" ;
rep [ "F" ] = "F#" ;
rep [ "F#" ] = "G" ;
rep [ "G" ] = "G#" ;
string muse = " C D# E " ;
System.Text.StringBuilder token = new System.Text.StringBuilder ( muse.Length ) ;
System.Text.StringBuilder result = new System.Text.StringBuilder ( muse.Length ) ;
for ( int i = 0 ; i < muse.Length ; i++ )
{
char ch = muse [ i ] ;
if ( !System.Char.IsWhiteSpace ( ch ) )
{
token.Append ( ch ) ;
}
else
{
if ( token.Length > 0 )
{
string tok = token.ToString() ;
if ( rep.ContainsKey ( tok ) )
{
result.Append ( rep [ tok ] ) ;
}
else
{
result.Append ( tok ) ;
}
token.Length = 0 ;
}
result.Append ( ch ) ;
}
}