Joben

O primă observaţie necesară pentru a rezolva această problemă este că niciodată nu este nevoie să facem mai mult de o permutare şi o transformare pentru a obţine şirul dorit, în cazul în care există soluţie. De asemenea, ordinea în care aplicăm operaţiile nu are nicio relevanţă. Dacă am aplica doar o operaţie de permutare, condiţia necesară şi suficientă pentru existenţa unei soluţii este ca frecvenţa fiecărei litere din primul şir să coincidă cu frecvenţa ei din al doilea şir. Aplicând şi o operaţie de transformare, pentru fiecare frecvenţă de literă din primul şir trebuie indentificată o frecvenţă de literă din al doilea şir egală cu ea astfel încât oricare două litere din primul şir să aibă corespondenţi diferiţi. Cea mai simplă metodă de a face această verificare este să sortăm cei doi vectori de frecvenţă şi apoi să-i comparăm element cu element.