I guess they won't break correctness but I do remember many algorithms (e.g. tries) assume you have constant random access to characters which AFAIK is not poss

I guess they won't break correctness but I do remember many algorithms (e.g. tries) assume you have constant random access to characters which AFAIK is not possible in UTF-8