poligrama.cpp

#include <bits/stdc++.h>

using namespace std;
int freq[26];

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    // 'i' é o tamanho da raiz que estamos procurando
    for (int i = 1; i < n; i++) {
        if (n % i != 0) continue;

        for (int i = 0; i < 26; i++)
            freq[i] = 0;

        // Frequências da "raiz"
        for (int j = 0; j < i; j++)
            freq[s[j] - 'a']++;

        bool certo = true;
        // Outras strings
        for (int k = i; k < n; k += i) {

            // Comparar a frequência dessa string com a "raiz"
            for (int j = k; j < k + i; j++) {
                // Se a frequência dessa letra for 0, significa que ela não existe na "raiz".
                if (freq[s[j] - 'a'] == 0) {
                    certo = false;
                    break;
                }
                freq[s[j] - 'a']--; // Subtrair a letra atual do vetor de frequências.
            }

            if (!certo)
                break;

            // Como todas as strings tem o mesmo tamanho da "raiz", o vetor de frequência estará zerado e
            // temos certeza que essa string é um anagrama da raiz.
            // Para testar a próxima string, precisamos remontar o vetor de frequência.

            // Frequências da "raiz"
            for (int j = 0; j < i; j++)
                freq[s[j] - 'a']++;
        }

        // Assim que achamos a resposta já podemos retornar, pois ele quer a menor resposta.
        if (certo) {
            for (int j = 0; j < i; j++) // Imprime a "raiz"
                cout << s[j];

            cout << '\n';
            return 0;
        }
    }
    cout << "*\n";
    return 0;
}