Substitution in c

The best decoding attempt I ever got was this. Explanations in the code:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_STR 1000
#define NUM_LETRAS 26

int main() {

    int i, j;

    char alfabeto[] = "abcdefghijklmnopqrstuvwxyz";
    char ordem[] = "aeosrdnitmulcvpgqbfhjxzkyw";
    char trocas[] = "jgmfri";
    char chave[NUM_LETRAS + 1]; // + 1 por causa do terminador da string.
    int frequencias[NUM_LETRAS];
    int frequencias2[NUM_LETRAS];
    char codificado[MAX_STR];
    char decodificado[MAX_STR];

    // Passo 1:
    // Limpa o vetor "frequencias".
    for (i = 0; i < NUM_LETRAS; i++) {
        frequencias[i] = 0;
    }

    // Passo 2:
    // Lê a string codificada do usuário.
    printf("Digite o texto criptografado: ");
    fgets(codificado, MAX_STR, stdin);

    // Passo 3:
    // Percorre a string "codificado" e conta quantas vezes cada letra aparece,
    // guardando a contagem no vetor "frequencias".
    for (i = 0; codificado[i]; i++) {
        if (codificado[i] >= 'a' && codificado[i] <= 'z') { // Se for letra minúscula.
            frequencias[codificado[i] - 'a']++;
        } else if (codificado[i] >= 'A' && codificado[i] <= 'Z') { // Se for letra maiúscula.
            frequencias[codificado[i] - 'A']++;
        }
        // Poderia ter um else para os casos onde não é nenhum dos dois,
        // mas quando isso acontece, não precisamos fazer nada.
    }

    // Passo 4 (opcional):
    // Mostra o vetor "frequencias".
    // Aproveita para copiar "frequencias" para "frequencias2".
    printf("\n\nTabela de frequências:");
    for (i = 0; i < NUM_LETRAS; i++) {
        printf(" %c=%d", i + 'a', frequencias[i]);
        frequencias2[i] = frequencias[i];
    }
    printf("\n");

    // Passo 5:
    // Percorre a tabela "frequencias" para montar a "chave", utilizando a ordem das letras
    // dada pelo vetor "ordem". Entretanto, o vetor "frequencias" acaba sendo destruído
    // por esse processo, e é por isso que temos uma cópia em "frequencias2".
    for (i = 0; i < NUM_LETRAS; i++) {
        int maior = -1;
        int maior_indice = 0;
        for (j = 0; j < NUM_LETRAS; j++) {
            if (frequencias[j] >= maior) {
                maior = frequencias[j];
                maior_indice = j;
            }
        }
        chave[maior_indice] = ordem[i];
        frequencias[maior_indice] = -1;
    }
    chave[NUM_LETRAS] = 0;

    // Passo 6 (opcional):
    // Percorre a tabela "frequencias2" para procurar por letras que ocorram um mesmo
    // número de vezes (que não seja zero) e mostrar isso ao usuário.
    // Entretanto, "frequencias2" acaba sendo destruído nesse processo.
    for (i = 0; i < NUM_LETRAS; i++) {
        if (frequencias2[i] == 0) continue;
        int p = 0;
        for (j = i + 1; j < NUM_LETRAS; j++) {
            if (frequencias2[j] != frequencias2[i]) continue;
            if (p == 0) {
                printf("Frequências iguais [%d]: %c", frequencias2[i], i + 'a');
                p = 1;
            }
            printf("%c", (j + 'a'));
            frequencias2[j] = 0;
        }
        frequencias2[i] = 0;
        if (p != 0) printf("\n");
    }

    // Passo 7 (opcional):
    // Troca algumas letras da "chave" a fim de ajeitar manualmente os casos que estiverem errados.
    // As letras das posições pares são permutadas com as das posições ímpares de "trocas".
    for (i = 0; trocas[i]; i += 2) {
        char temp = chave[trocas[i] - 'a'];
        chave[trocas[i] - 'a'] = chave[trocas[i + 1] - 'a'];
        chave[trocas[i + 1] - 'a'] = temp;
    }

    // Passo 8 (opcional):
    // Mostra a chave.
    printf("\nA chave é:\n%s\n%s\n", alfabeto, chave);

    // Passo 9:
    // Tendo o vetor "chave" montado, usa ele para formar a string "decodificado"
    // a partir de "codificado".
    for (i = 0; codificado[i]; i++) {
        if (codificado[i] >= 'a' && codificado[i] <= 'z') { // Letras minúsculas.
            decodificado[i] = chave[codificado[i] - 'a'];
        } else if (codificado[i] >= 'A' && codificado[i] <= 'Z') { // Letras maiúsculas.
            decodificado[i] = chave[codificado[i] - 'A'] - 'a' + 'A';
        } else { // Copia qualquer outra coisa diretamente.
            decodificado[i] = codificado[i];
        }
    }
    decodificado[i] = codificado[i]; // Copia o terminador nulo.

    // Passo 10:
    // Mostra o texto "decodificado".
    printf("\nO texto descriptografado é:\n%s\n", decodificado);  
}

Here's the output:

Digite o texto criptografado: 

Tabela de frequências: a=1 b=6 c=36 d=0 e=6 f=13 g=9 h=1 i=3 j=8 k=4 l=0 m=14 n=11 o=2 p=2 q=0 r=2 s=18 t=0 u=0 v=6 w=4 x=8 y=0 z=18
Frequências iguais [1]: ah
Frequências iguais [6]: bev
Frequências iguais [8]: jx
Frequências iguais [4]: kw
Frequências iguais [2]: opr
Frequências iguais [18]: sz

A chave é:
abcdefghijklmnopqrstuvwxyz
hlawustfgnvyrdbqkpozxmcije

O texto descriptografado é:
Aoariaoesobarseoaoondacatsoquetasvntedmaclranacuonmadalsriareodudvateadmeodahegatsolaooaraiandtaaceitamalrsbadaeilerngsoeguerraoeopsrvatsoianotsquelrsiemnaapsrvafuiadaeedmr

See here working on ideone.

Note the decrypted text:

  

However, I had to force some letter changes (with the trocas array). The exchanges were (in the key), J with G, M with F and R with I. I found these possible exchanges on the basis of trial and error, and kick. Without these changes, the text produced is this:

  

And then, you will have to have the inglorious task of kicking several possible exchanges until you find the correct result.

An approach that tries several possible combinations of exchanges and looks at how the largest number of words in a given dictionary with tens of thousands of words would be a possibility, but this is clearly far from the one proposed in this problem.

If the encrypted text had spaces, the task would be much easier.