Maksimalni proizvod dužina nepovezanih reči

Dati su niz reči i potrebno je pronaći maksimalni proizvod dužina dve reči koje nemaju nijedan zajednički karakter. Svaka reč može sadržati mala slova engleske abecede (a do z). Dve reči se smatraju "nepovezanim" ako ne dele nijednu istu slovo u svojoj binarnoj reprezentaciji.

Za svaku kombinaciju dve reči, ako ne dele nijedno slovo, izračunava se proizvod njihovih dužina, a cilj je pronaći maksimalnu vrednost tog proizvoda.

Ako ne postoji nijedna kombinacija reči koje nemaju zajedničkih karaktera, potrebno je vratiti -1 na standardan izlaz za greške.

Ulaz

Prvi red ulaza sadrži celobrojni broj n $(1 ≤ n ≤ 100)$, broj reči u nizu.
U narednih n redova nalazi se po jedna reč, i, gde je svaka reč niz malih slova engleske abecede. Dužina svake reči može biti do 100 karaktera.

Izlaz

Ako postoje dve reči koje nemaju zajedničkih karaktera, treba ispisati maksimalni proizvod njihovih dužina na standardan izlaz.
Ako nema takvih reči, treba ispisati -1 na standardan izlaz za greške.

Primer 1

Ulaz

6
abcw
baz
foo
bar
xtfn
abcdef

Izlaz

Primer 2

Ulaz

3
abc
abz
abx

Izlaz

Na stderr ispisujemo:

-1

Rešenje

`main.c`

#include <stdio.h>

int max_proizvod_duzina(char** reci, int broj_reci){
	int *maske = (int*)malloc(broj_reci * sizeof(int));

	for (int i = 0; i < broj_reci; i++) {
        maske[i] = 0;
        for (int j = 0; reci[i][j] != '\0'; j++) {
            maske[i] |= 1 << (reci[i][j] - 'a');  // Postavljamo odgovarajući bit
        }
    }

	int max_proizvod = -1;
	for (int i = 0; i < broj_reci; i++) {
        for (int j = 0; j < i; j++) {
            if ((maske[i] & maske[j]) == 0) {  // Ako ne dele zajedničke karaktere
                int proizvod = strlen(reci[i]) * strlen(reci[j]);
                if (proizvod > max_proizvod) {
                    max_proizvod = proizvod;  // Ažuriramo maksimalni proizvod
                }
            }
        }
    }

    free(maske);
	return max_proizvod;
}

int main(void)
{
	int n;
    scanf("%d", &n);

    char** words = (char**)malloc(n * sizeof(char*));

    for (int i = 0; i < n; i++) {
        words[i] = (char*)malloc(100 * sizeof(char));  // Pretpostavljamo maksimalnu dužinu reči 100
        scanf("%s", words[i]);
    }

	int rezultat = max_proizvod_duzina(words, n);

	if (rezultat == -1) {
        fprintf(stderr, "-1\n");
    } else {
        printf("%d\n", rezultat);
    }

    for (int i = 0; i < n; i++) {
        free(words[i]);
    }
    free(words);

	return 0;
}