Escrito por Thiago Mota
Para começar iremos resolver um problema mais simples, dado duas palavras, diga se elas são ou não anagramas uma da outra. Existe várias maneiras rápidas de fazer isso, a mais útil e fácil para questão agora é ordenar as letras de cada palavra, pois se duas são anagramas suas letras devem ficar ordenadas igualmente.
Ou seja, ordenando as letras de cada palavra, basta checar se as palavras são iguais após a ordenação. No problema original podemos ordenar as letras de cada palavra, fazendo o problema virar qual a palavra que possuí o maior número de ocorrências, assim como no exemplo acima, para isso basta guardar um map<string, int> que informa a frequência (número de vezes) que cada palavra aparece após a ordenação, e no final basta imprimir a maior frequência. Segue o código.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Solucao Intermediário Semana 59 - Anagramas | |
| // Thiago Mota | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 100010; | |
| map<string, int> freq; | |
| string str[maxn]; | |
| int main() { | |
| int n; | |
| cin >> n; | |
| for(int i = 1; i <= n; i++) { | |
| string str; | |
| cin >> str; // Ler a palavra; | |
| sort(str.begin(), str.end()); // Ordernar a palavra pelas letras (roma = amor, dcba = abcd) | |
| freq[str]++; // Aumenta a frequencia da palavra | |
| } | |
| int ans = 0; // Maior frequencia | |
| for(map<string, int>::iterator it = freq.begin(); it != freq.end(); it++) { // Olhar para cada palavra armazenada em freq | |
| string s = (*it).first; // Palavra armazenada | |
| int f = (*it).second; // Frequencia da palavra | |
| if(f > ans) { | |
| ans = f; // Se a frequencia da palavra s for maior que a resposta, atualiza a resposta | |
| } | |
| } | |
| cout << ans << "\n"; | |
| return 0; | |
| } |