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 Hollandais", 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)...

Je pense qu'il doit falloir sans doute commencer par remplacer les X de la manière suivante :
XXXXX -> CBACB
Puis les trier avec un algorithme efficace mais cela fait déjà 8 heures que je me casse la tête dessus et je n'ai toujours trouvé aucune solution améliorant ne serait ce qu'un peu la complexité... J'ai essayé d'adapter différents algorithme de tri connu en programmation mais les appliqués sur la machine de turing augmente énormément leur complexité.

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