Zauważmy, że są 3 możliwe najlepsze powtarzalności:
jeżeli wszystkie litery są takie same, to słowo będzie miało powtarzalność $n-1$ i nie możemy nic zmienić. (np. “aaaaaaaaa”)
jeżeli istnieje chociaż jedna litera która występuje w tym słowie dokładnie raz, to możemy ją dać na pierwsze
miejsce i powtarzalność będzie równa 0. Możemy więc posortować leksykograficznie resztę słowa. (np. “caabbefg”)
w przeciwnym wypadku istnieje przynajmniej jedna litera która występuje conajmniej 2, ale nie więcej niż $n/2 + 1$ razy.
Możemy więc dać 2 te litery na początek, a potem na zmianę tą literę i jakąś inną, otrzymując powtarzalność 1.
Jedyny nietrywialny przypadek to ten trzeci, możemy go rozbić na 3 mniejsze przypadki:
jeżeli najmniejsza leksykograficznie litera występująca w słowie nie występuje więcej niż $n/2 + 1$ razy to dajemy 2 te litery
na początek, resztę sortujemy leksykograficznie i dajemy na zmianę inną literę i tą najmniejszą aż się skończą. (np. “aabacadadefg”)
w przeciwnym wypadkum, jeżeli w całym słowie występują dokładnie 2 różne litery, dajemy jedną najmniejszą leksykograficznie literę na początek,
potem wszystkie drugiego rodzaju i na końcu resztę tego pierwszego. (np. “abbbbbaaaaaaaa”).
w przeciwnym wypadku, dajemy jedną najmniejszą leksykograficznie literę na początek, potem jedną drugą najmniejszą, potem resztę
pierwszej i na końcu całą resztę posortowaną leksykograficznie. (np. “abbbbbaaaaaaaa”).