An interesting alternate idea, though I fear the constant factor may be too high for a language like Java, especially given Java's whole lack-of-value-types thi

An interesting alternate idea, though I fear the constant factor may be too high for a language like Java, especially given Java's whole lack-of-value-types thing. (And Java 8's "value types" don't work for this, due to their immutability. Yay.) You store a string as a self-balancing tree, preferably one that supports constant-time appends and prepends.(For example, a skew-binary random access list or a finger tree.) Each node of the tree has an encoding enum, an array (+ length of said array), and the length including children (alternatively, the length of the left child). A node's characters are all the same length given by the encoding of the node, and a node stores characters by grapheme clusters. This allows efficient string building, among other things. About the only problems are that lookup/replacement in the middle of strings is now O(log n), and the constant factor. So, for example, if you have the string "This is a t̴̟̟͙̞̑ͩ͌͝est", it'd (probably) be stored in three nodes: one that stores "This is a t" with an encoding of one byte per character, a direct lookup into the first 256 unicode characters, one that stores "̴̴̟̟͙̞̟̟͙̞̑ͩ͌̑ͩ͌͝͝e", with an encoding of, what, 20 bytes per character, utf8 within a character, and one that stores "st", same as the start. Unfortunately, Java has too much overhead to make this practical.