Also, if you want O(1) indexing by grapheme cluster you can get that with less memory overhead by precomputing a lookup table of the location in the string where you can find every k-th grapheme cluster, for some constant k >= 1. (This requires a single O(n) pass through the string to build the index, but you were always going to have do make at least one such pass through the string for other reasons.)