O(n) is only an issue for large strings - let's say it might start being a concern at n > 1024, although for modern systems quite frankly n can be substantially

O(n) is only an issue for large strings - let's say it might start being a concern at n > 1024, although for modern systems quite frankly n can be substantially larger without incurring any noticeable time loss. In my 20 year career, it has been rare to deal with strings larger than 1024 characters. In those cases, I don't think it's unreasonable to have to use a specialised class that tracks string indexing such that lookup becomes O(1). With enough mucking around you can even get insertion to be O(1). For the remaining use cases of strings (the vast majority - filenames, URLs, UI labels, database fields), O(n) performance is perfectly adequate. This is why UTF-8 is such a successful hack.