If substrings are the issue, then you can have your cake and eat it too.
Make every string a structure with a length, offset, and a pointer to a string storage structure. Make the string storage structure have a maximum length and a pointer to the start of the actual string data. The string data is just an array of bytes.
The space is allocated in powers of 2. If you go to append and you still have room, you just insert the data. Otherwise you reallocate room, move the existing string, free the old space and allocate at the new place. This makes incremental appends perform just fine. Taking substrings is just as fast. The overhead is seen from following one extra pointer when finding the string.
This is not entirely dissimilar to what you find in, say, Perl or Ruby. (Neither is exactly like this. though I think that Ruby is closer. A lot closer.) It makes building up large strings incrementally perform just fine. Substrings can be taken efficiently (well not in Perl - but look at how Ruby implements backreferences lazily for instance).
But even so in Ruby the += operator is *still* slow, for exactly the technical reason given above. You are creating lots of new objects. Why? Well, very simple. += has defined semantic effects. You can't get those semantic effects without creating new objects. If you want an efficient string append you have to use the special << operator because the semantic effects are visible. Observe:
# Create 2 strings
init_a = "Hello";
init_b = "Hello";
# Duplicate them.
dup_a = init_a;
dup_b = init_b;
# Append to the dups
dup_a += ", World";
dup_b << ", World";
# What do we have?
puts "init_a is '#{init_a}'"; #-> "Hello"
puts "init_b is '#{init_b}'"; #-> "Hello, World"
puts "dup_a is '#{dup_a}'"; #-> "Hello, World"
puts "dup_b is '#{dup_a}'"; #-> "Hello, World"
And there we see why, even with smart data structures where efficiency is achievable, the += operator still has to be slow.
Cheers,
Ben