[FlaminSarge]

You'd still have to iterate through the trie's keys, and for that you need an array. Think about it:
1) Parse string, find { } tags. Save these locations somewhere.
2) At each location, check to see if the tag matches any color tags. You'll need to check every key in the trie, but you can't iterate through tries, so you'll need to go through some other thing that stores the keys. That's what the array's for (you could use the non-ADT array, but that won't have dynamic sizing so you'd have to have a MAX_COLORS define).
3) You replace those with empty space. You'd have to move all other pieces of the string down to where the tag is removed.

I believe in either case, you'd need something like that. Using ReplaceString and iterating through the array is much easier than manually editing the string like that.

If you're worried about space, you could make this a plugin, and then all plugins using it would share the same set of colors, and each time you added a color all plugins would get that color. That may or may not be a good thing.