Are you sure they are the reason for the memory error? String literals don't take up much memory, unless they are either very very long or very very numerous.
Are you even sure they are String literals, and not non-interned Strings? These should be garbage collected as usual.
Part of your problem may be that you are still holding a reference to them, or perhaps to their internal char. When you call substring on a String, that substring shares the original String's char. If the substring is much smaller than the original, that is a waste of memory. This is one of the few cases where using copying the String makes sense. So if this is the case, use the following to create substrings:
This will create a new String that does not share the char, and therefore this char can be garbage collected too.