Machines de Turing, Complexité et "Drapeau Belge"

Bonjour à tous!

Tout d'abord, merci à ceux qui prendront le temps de me lire :)

Je vous explique mon problème :

je dois réaliser une machine de turing (à un ruban, considéré comme infini des deux côtés) qui règle le problème dit du "Drapeau Belge", c'est à dire remplace par une série d'un caractère défini par un tiers de A, un tiers de B et un tiers de C, avec A <= B <= C

Par exemple :
xxx => ABC
xxxx => ABCC
xxxxx => ABBCC
xxxxxx => AABBCC
etc...

J'ai déjà trouvé deux solutions différentes :
* Faire une marque tous les trois caractères, remplacer le nombre de marques par des C a la fin, puis remplacer le reste en mettant un B à droite, un A à gauche, etc...
* Partir sur une base ABC, et à chaque nouveau caractère, ajouter la bonne lettre et décaler l'existant (par exemple, on remplace le premier B par un A, le premier C par un B, et le nouveau caractère par un C).

Si ces deux solutions donnent le résultat souhaité, elles ne sont pas assez performantes. En effet, leur complexité est de l'ordre de n² (avec n le nombre d'éléments à remplacer), et je cherche une solution en n.log(n)...

La machine de turing ne pouvant que faire des actions de base (décaler la tête de lecture à gauche, décaler la tête de lecture à droite, lire et écrire), et n'ayant qu'un seul ruban (donc une seule tête de lecture), je ne trouve pas de solution me permettant de me passer des allers/retours qui font augmenter ma complexité...

Si quelqu'un a une idée, une piste, ou des questions... Merci à vous!