BastterCode semana 8 - 2423 Remove Letter To Equalize Frequency
comentada em 07/03/2023 09:29

from collections import Counter

def word_even(word: str) -> bool:
    x = 0
    verdade = False
    while(x<len(word)):
        verificador = False   
        while(verificador == False):
            for i in range(len(word)):
                new_str = list(word[:i] + word[i+1:])
                moda = list(dict.values(Counter(new_str)))
                x+=1
                if sum(moda) == len(moda):
                    verificador = True
                    verdade = True
            verificador = True
    
    return verdade

Esse eu comecei a fazer ontem, depois que vi a sugestão do Rod100.

Segue o código, depois vejo como posso dar uma melhorada nele. 

class Solution {
public:
    bool equalFrequency(string word) 

//input é uma sequência de caracteres
    
{

/* algoritmo vai mapear a frequência de cada
caractere e depois vai mapear a frequência de
cada frequência. 

Ou seja, se a letra "a" aparecer 2x e a "b"
aparecer 1x, então o primeiro mapa seria:
(a->2, b-> 1) e o segundo seria (2->1, 1->1).

Se houver mais de 2 frequências, retirar 1
letra jamais equalizarâ aa frequências, não
importando quantas letras haja para cada dessas
frequências. 

Se houver apenas 1 frequência e ela for 1,
significa que cada letra aparece 1 única vez.
Nesse caso, retirar qualquer uma sempre manterá
a frequência equalizada. 

Se houver apenas 1 frequência e o n° de letras
da string for 1, significa que a string é uma
sequência de repetições da mesma letra e retirar
qualquer elemento manterá a frequência equalizada.

Se houver 2 frequências e ambas aparecerem mais de
1 vez, então há mais de uma letra em cada frequência
e retirar apenas 1 letra não eliminará a frequência
correspondente. Isso significa que as frequências não
podem ser equalizadas. 

Se houver 2 frequências e uma delas aparecer 1 vez, a
frequência poderá ser equalizada em duas situações:

A- se essa frequência que aparece 1 vez for 1, ou 
seja, 1 letra aparece 1 vez, caso em que ela pode ser 
eliminada e a frequência deixa de existir, sobrando 
apenas 1 frequência na palavra; ou

B- se essa frequência que aparece 1 vez tiver um n° de
elementos X tal que X-1 corresponder à outra frequência 
mapeada. Ou seja, há por exemplo 1 letra que aparece 3
vezes e 4 que aparecem 2 vezes. Se for retirada 1 das
repetições da letra que aparece 3 veses, ela apareceria
2 vezes, a mesma frequência das demais letras. */

      map<char, int> mapl;
      map<int, int> mapi;

//mapeando a frequência de cada letra
      
      for (int i = 0; i < word.size(); i++)
      {
        int index = word[i];
        if (mapl.count(index))
        {
          mapl[index]++;
        } else
        {
          mapl[index] = 1;
        }
      }
      
//mapeando a frequência de cada frequência

      for (std::map<char,int>:: iterator it = mapl.begin();
 it != mapl.end(); it++)
      {
        int index = it->second;
        if (mapi.count(index))
        {
          mapi[index]++;
        } else
        {
          mapi[index] = 1;
        }
      }

//aplicando as condicionais explicadas acima
//se houver mais de 2 frequências, é impossível equalizar

      if (mapi.size() > 2)
      {
        return false;
      } 
       
      for (std::map<int,int>:: iterator it = mapi.begin(); 
it != mapi.end(); it++)
      {

//se houver 1 frequência e ela for 1 ou se
//houver apenas uma letra repetida, o retorno é true
//equivalentemente, o retorno é false se ambas as
//condições forem falsas (negação de X||Y é !X&&!Y)

        if (mapi.size() == 1)
        {
          if (it->first != 1 && mapl.size() != 1)
          {
            return false;
          }
        } 

//se houver 2 frequências, 1 delas aparecer apenas 1
//vez e for 1 ou for tal que, se reduzida em 1, iguala
//a outra frequência, retorna true. Em qualquer outro
//caso, retorna false. 
        
        if (mapi.size() == 2)
        {

           if (it->second == 1)
           {
              if (mapi.count(it->first-1) || 
(it->first == 1))
              {
                return true;
              } else if (it != mapi.begin())
              {
                return false;
              } 
           } 
             else if (it != mapi.begin())
           {
             return false;
           }
        }
        
      }      

    return true;
       
    }
};?

como bom programador tabajara, não consegui prever de antemão todos os casos possíveis

fiz a função e depois tive que acrescentar mais condições à medida que os erros apareciam, kkkk

solução mais rápida de fazer, tira, conta e ve se ficou bom. é o bom e velho "tentativa e erro". Achei que o desempenho seria pior, mas ficou ok,

bool equalFrequency(char * word){

    int len = strlen(word);
    int i,j,k;
    int freq[26];
    int maxfreq;
    int minfreq;
    for(i=0;i<len;i++){
        maxfreq = -1;
        minfreq = 101;

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

        for(j=0;j<len;j++)
            if(i!=j)
                freq[word[j]-'a']++;

        for(k=0;k<26;k++){
            if(freq[k]>maxfreq)
                maxfreq = freq[k];
            if(freq[k]<minfreq&&freq[k])
                minfreq = freq[k];
        }
        
  
        if(maxfreq==minfreq)
            return true;
    }

    return false;
}   ?

from collections import Counter
class Solution:
    def equalFrequency(self, word: str) -> bool:
        letter_counts = Counter(word)

        # Dropping most common letter
        most_common_letter = letter_counts.most_common()[0][0][0]

        letter_counts[most_common_letter] -= 1
        letter_counts = +letter_counts  # Only keep counts > 0
        nunique_counts_dropping_most_common = len(set(letter_counts.values()))
        letter_counts[most_common_letter] += 1  # Reset most common count
        
        # Dropping least common letter
        least_common_letter = letter_counts.most_common()[-1][0][0]

        letter_counts[least_common_letter] -= 1
        letter_counts = +letter_counts
        nunique_counts_dropping_least_common = len(set(letter_counts.values()))
        
        return (nunique_counts_dropping_most_common == 1
                or nunique_counts_dropping_least_common == 1)

Ver mais

Eu tentei fazer sem um segundo map, usando contadores manuais para verificar as condições. Deu um trabalhão! kkkk

class Solution {
public:
    bool equalFrequency(string word) {
        map<char, int> mapl;
        int count_1 = 0, count_2 = 0, count_3 = 0, count_4 = 0;        

        for (int i = 0; i < word.size(); i++) {
            char index = word[i];
            if (mapl.count(index)) {mapl[index]++;}
            else {mapl[index] = 1;}
        }

        int size = mapl.size();

        for (std::map<char,int>::iterator it_1 = mapl.begin();
        it_1 != mapl.end(); it_1++) {
            int freq_1 = it_1->second;
            int sum = 0;
            for (std::map<char,int>::iterator it_2 = mapl.begin();
            it_2 != mapl.end(); it_2++) {
                int freq_2 = it_2->second;                
                if (it_1 != it_2) {
                    if (freq_1 >= freq_2) {
                        if (freq_1 - freq_2 == 1) {count_1++; sum++;}
                        if (freq_1 - freq_2 > 1) {count_2++;}
                        if (freq_1 - freq_2 < 1) {count_3++;}
                        if (freq_2 == 1) {count_4++;}
                    }
                }                                       
            }
            if (sum > 0 && sum != size - 1) {count_1 = 0;}
        }        

        if (count_4 == size*(size - 1)) {return true;}
        if (count_4 == size - 1) {
            if (count_3 == (size - 1)*(size - 2)) {return true;}
        }
        if (count_2 == 0) {
            if (count_1 == size - 1) {return true;}
        }              
        return false;        
    }
};?

Aqui embaixo o mesmo código lá de cima, só que mais organizado e sem a confusão de retorno true e false.

class Solution {
public:
    bool equalFrequency(string word) {
        map<char, int> mapl;
        map<int, int> mapi;
      
        for (int i = 0; i < word.size(); i++) {
            char index = word[i];
            if (mapl.count(index)) {mapl[index]++;} 
            else {mapl[index] = 1;}
        }
      
        for (std::map<char,int>:: iterator it = mapl.begin();
        it != mapl.end(); it++) {
            int index = it->second;
            if (mapi.count(index)) {mapi[index]++;} 
            else {mapi[index] = 1;}
        }       

        for (std::map<int,int>:: iterator it = mapi.begin();
        it != mapi.end(); it++) {
            if (mapi.size() == 1) {
                if (it->first == 1 || mapl.size() == 1) {return true;}
            }        
            if (mapi.size() == 2 && it->second == 1) {
                if (mapi.count(it->first-1) || (it->first == 1)) {
                    return true;
                }                 
            }              
        }        
        return false;       
    }
};

@Giovanni

Como eu falei lá no outro tópico, eu sou noob e não tenho condição de saber se uma questão é, ou não, boa.

Mas como você tá pedindo pra sugerir, filtrei pelas questões fáceis, top interview questions e pela tag "divide and conquer" (pra aproveitar já a lição do FlyCavok no outro tópico). Apareceram quatro opções, escolhi a que tinha a menor acceptance:

LeetCode - The World's Leading Online Programming Learning Platform

Já tinha resolvido esse problema, mas foi na força bruta, removia um caractere por vez e verificava se dava certo. Hoje busquei uma solução mais "limpa". Está aí abaixo.

class Solution {
    fun equalFrequency(word: String): Boolean {

        // map for assONciating a char with its frequency
        var charCounter = mutableMapOf<Char,Int>()
        // loop to count chars and store in charCounter
        for (char in word){
            // if map contains the letter as key, adds 1 to its own value
            if (charCounter.containsKey(char)){
                charCounter[char] = charCounter[char]!! + 1
            // if map does not contain the letter, must
            // include it in the map with value 1 (first occurence)
            } else charCounter[char] = 1
        }

        //listOfValues stores a list of the map values
        var listOfValues = mutableListOf<Int>()
        charCounter.forEach {entry ->
            listOfValues.add(entry.value)
        }

        // a copy is created to play with listOfValues while
        // listOfValues is never changed
        var copy = mutableListOf<Int>()

        // for every item in the list
        for (i in listOfValues.indices){
            // copy is reset to original listOfValues list
            copy = listOfValues.toMutableList()
            // one single item in list is reduced in 1
            copy[i] = copy[i] - 1
            // if that item became zero, it's removed from list
            if (copy[i] == 0) copy.remove(0) 
            // if max and min are equal, all items in list are equal, so return true
            if (copy.max() == copy.min()) return true 
        }
        // if never true, it's false
        return false
    }
}?

class Solution:
    def equalFrequency(self, word: str) -> bool:
        freq = [word.count(i) for i in dict.fromkeys(word)]
        
        for index, value in enumerate(freq):
            copy = freq.copy()
            copy[index] = value - 1
            if 0 in copy: copy.remove(0)
            status = len(set(copy)) == 1
            if status: break
        return status

@Giovanni faltou atualizar o link do banner, ainda tá com o tópico da semana passada.

Uma nova forma de se fazer, muito parecida com a anterior, só que usando as propriedades da multiplicação pra facilitar o trabalho.

Resumindo, eu transformo todos os caracteres na sua representação em números inteiros (os chars são armazenados como inteiros no C++), somo todas as letras da string em uma variável e também somo cada letra uma vez em outra variável.

Se a frequência de todos os caracteres for igual então a soma do produto entre cada caractere e sua frequência é igual ao produto dessa frequência com a soma dos caracteres.

Pra ficar melhor de visualizar:

freq*('a') + freq*('b') +.... + freq*('z') = freq*('a' + 'b' + ... + 'z')

É a propriedade distributiva da multiplicação.

Aí é só questão de operacionalizar isso, passando o for por todos os caracteres da string 2x (uma para fazer as somas e a segunda para realizar os testes).

Os testes levam em conta a retirada de cada caractere, então, se a frequência do caractere em questão for 1, ele é retirado da string totalmente. Por isso é preciso uma segunda variável para armazenar o valor do caractere anterior, permitindo usar a frequência dele.

É apenas uma variação do código anterior que me ocorreu no trânsito e que permite um código um pouco mais limpinho, sem precisar de mais de um for nem de um monte de if aninhado.

bool equalFrequency(string word) {
    int sum_tot = 0, sum_val = 0;
    int size = word.size(), p_num = 0;
    map<int,int> freq;

    for (int i = 0; i < 2*size; i++) {
        int num = static_cast<int>(word[i % size]);            
        if (i < size) {
            sum_tot += num;
            if (freq.count(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
                sum_val += num;
            }
        } 
        else 
        if (sum_tot - num == (freq[num] - 1)*sum_val) {
            return true;
        } else 
        if (sum_tot - num == freq[p_num]*(sum_val - num)) {
            return true;
        }
        p_num = num;
    }
    return false;        
    }?

Como esse exercício é classificado como Easy é algo que me assusta hahaha

Também fiz na base do testa, buga, corrige.

Segue o código implementado. Não usei nenhum dicionário, só manipulação de Arrays

Time: O(n) 
Memory: O(1)

Linguagem: C#

public class Solution {
    public bool EqualFrequency(string word) {
        int [] freqs = new int[26];
        int n = word.Length;

        // we have only 26 chars possible. This fill a frequency array in O(n)
        for (int i = 0; i < n; i++) {
            freqs[word[i]-'a']++;
        }

        int [] frequenciesFound = new int[2] { -1, -1 };
        int [] numCharsWithSameFrequency = new int[2] { 0, 0 };
        int freqChkCount = 0;
        for (int i = 0; i < freqs.Length; i++) {
            if (freqs[i] <= 0) continue;
            
            if (frequenciesFound[0] == freqs[i]) {
                numCharsWithSameFrequency[0]++;
                continue;
            
            } else if (frequenciesFound[0] < 0) {
                    frequenciesFound[0] = freqs[i];
                    numCharsWithSameFrequency[0] = 1;
                    freqChkCount++;
                    continue;
            }
            
            if (frequenciesFound[1] == freqs[i]) {
                numCharsWithSameFrequency[1]++;
                continue;
            
            } else if (frequenciesFound[1] < 0) {
                    frequenciesFound[1] = freqs[i];
                    numCharsWithSameFrequency[1] = 1;
                    freqChkCount++;
                    continue;
            }

            // trying to add a third frequency results in failure
            return false;
        }

        if (freqChkCount == 1) {
            return numCharsWithSameFrequency[0] == 1 // only one char was found
            || frequenciesFound[0] == 1;  // many chars are found, but all have frequency 1, so just remove any
        }

        // if not, then there are 2 frequencies

        // is there 1 element in slot 0? if so, it must be checked
        if (numCharsWithSameFrequency[0] == 1) {
            // if this element has frequency 1, then just remove it
            // or if it has frequency equals to 1 more element than guys on slot 1, then its also valid.
            if (frequenciesFound[0] == 1 || frequenciesFound[0] == frequenciesFound[1] + 1) return true;
        }

        // is there 1 element in slot 1? if so, it must be checked
        if (numCharsWithSameFrequency[1] == 1) {
            // if this element has frequency 1, then just remove it
            // or if it has frequency equals to 1 more element than guys on slot 0, then its also valid.
            if (frequenciesFound[1] == 1 || frequenciesFound[1] == frequenciesFound[0] + 1) return true;
        }
        
        return false;

    }
}?

Fiquei assustado

Ver mais

The function can_make_freq_equal takes a string word as input and returns True if it is possible to remove one letter from word so that the frequency of all letters in the resulting string are equal, and False otherwise.

The function first creates a dictionary freq that maps each character in word to its frequency. It then checks three conditions to determine if it is possible to remove one letter to make the frequency of all letters equal:

If the minimum and maximum frequency values are the same, then all letters in the string already have the same frequency, so we can simply return True.

If there is exactly one character with the minimum frequency, and that frequency is equal to 1, then we can remove that character to make all frequencies equal.

If there is exactly one character with the maximum frequency, and that frequency is one greater than the minimum frequency, then we can remove that character to make all frequencies equal.

If none of these conditions hold, then it is not possible to make the frequency of all letters equal by removing one letter, so the function returns False.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

bool can_make_freq_equal(string word) {
    unordered_map<char, int> freq;
    for (char c : word) {
        freq[c]++;
    }

    int min_val = INT_MAX;
    int max_val = INT_MIN;
    for (auto p : freq) {
        min_val = min(min_val, p.second);
        max_val = max(max_val, p.second);
    }

    if (min_val == max_val) {
        return true;
    }

    if (count(freq.begin(), freq.end(), min_val) == 1 && min_val == 1) {
        return true;
    }

    if (count(freq.begin(), freq.end(), max_val) == 1 && max_val == min_val + 1) {
        return true;
    }

    return false;
}

int main() {
    string word = "abbccc";
    if (can_make_freq_equal(word)) {
        cout << "It is possible to make the frequency of all letters equal by removing one letter." << endl;
    } else {
        cout << "It is not possible to make the frequency of all letters equal by removing one letter." << endl;
    }

    return 0;
}

ChatGPT tb em C++

@urbietorbi

Esse código não tá totalmente adequado.

É obrigatório tirar uma letra, então se a frequência for igual desde o começo, o retorno precisa ser falso a não ser que a frequência seja 1 (pois qualquer outra frequência, retirado um caractere, continua existindo num valor inferior e, portanto, sobrariam duas frequências na string). Além disso, se a frequência for 1, o retorno é verdadeiro independente de quantos caracteres tenham essa frequência.

Além disso, não basta que a frequência mínima seja 1 e ela tenha apenas 1 caractere, para ser verdadeiro não pode haver mais de duas frequências. Ele deveria ter testado por isso antes.

Por exemplo, na string "abbbccdddd", você tem 4 caracteres, um com frequência 1 ('a') e os demais com frequência 3 ('b'), 2 ('c') e 4 ('d'). Como a menor frequência é 1 e há apenas 1 caractere com essa frequência, o código dele retornaria verdadeiro, mas nessa string é impossível equalizar as frequências retirando apenas um caractere.

A única condição que tá ok mesmo é a última porque, se a frequência máxima for uma unidade superior da frequência mínima, então está implícito que há apenas duas frequências (já que as frequências são números inteiros e os inteiros só se incrementam de 1 em 1).

Minha primeira solução foi mais ou menos nessa mesma linha dele, dá uma olhada na explicação que eu coloquei lá.

Uma solução em Elixir

defmodule Solution do
  @spec equal_frequency(word :: String.t()) :: boolean
  def equal_frequency(word) do
    word
    |> String.codepoints()
    |> equal_freq?()
  end

  defp equal_freq?(next \\ [], curr)
  defp equal_freq?(_next, []), do: false

  defp equal_freq?(next, [head | rest]) do
    (next ++ rest)
    |> Enum.frequencies()
    |> Map.values()
    |> Enum.uniq()
    |> length()
    |> then(fn 
      1 -> true
      _else -> equal_freq?([head | next], rest)
    end)
  end
end

@oxe pode ser que vc esteja certo, pois não conferi o código, mas o chatgpt chegou muito próximo né? seria só o caso de fazer alguns ajustes.

@urbietorbi

Pelo que eu to vendo, o código do chatGPT tem o mesmo algoritmo, só em outra linguagem. Então acaba sofrendo do mesmo problema.

Eu tentei copiar e colar o código do chatGPT no leetcode e deu um monte de erro de sintaxe.

Mas eu digitei o código Python aí de cima, ele executou e deu resposta errada já no segundo teste. A palavra era "aazz", o código retornou true, quando o esperado era false.

É o que eu comentei ali em cima, como tem que tirar uma letra, então não pode retornar verdadeiro se as frequências forem iguais (a não ser que as frequências forem 1).

Eu não cheguei a corrigir o código porque infelizmente não sei mexer em Python. Mas é só levar em conta o que eu disse aí em cima.

Se colocar um teste anterior pra retornar falso se tiver mais de duas frequências e, nesse teste daí da igualdade entre min_val e max_val, colocar um AND para retornar verdadeiro se as frequências, além de serem iguais entre si, também forem iguais a 1, acho que o código já fica ok.

@oxe a primeira mensagem que eu postei nesse tópico, é um código meu, deu certinho, esse do chatgpt foi só para testar o poder da ferramenta mesmo.

@urbietorbi

O código que você postou dia 28/02 eu não testei. Mas esse em Python que você postou hoje às 14:50, que é o que eu to comentando, deu erro. Pelo que eu tinha entendido, o do chatGPT é o que você postou logo em seguida, em C++.

Ah, entendi agora. Ambos são do chatGPT, só em linguagens distintas. Por isso que é o mesmo algoritmo kkkk

Interessante, realmente chegou bem perto, só faltou uma condição e um ajuste em outra. E sugeriu uma abordagem nova, de pegar o maior e o menor valor, que acho que ninguém aqui ainda tinha pensado.

postado por @oxe em 03/03/2023 17:23

Ah, entendi agora. Ambos são do chatGPT, só em linguagens distintas. Por isso que é o mesmo algoritmo kkkk

Interessante, realmente chegou bem perto, só faltou uma condição e um ajuste em outra. E sugeriu uma abordagem nova, de pegar o maior e o menor valor, que acho que ninguém aqui ainda tinha pensado.

Isso, essa foi a razão de eu ter achado tão interessante

O código que submeti no dia 28/02/2023 às 22:30 comparou mínimo com máximo. Antes da comparação, se algum item na lista foi a zero, remove o zero da lista.

Olhando em retrospecto, o problema não é difícil, mas os dois exemplos dados no problema induzem a uma solução que não cobre todas as possibilidades. Logo, na hora de submeter o código, ocorre a falha para a string "abbcc".

Não tenho experiência como programador, mas acredito que este seja um problema bem recorrente em programação. É feita uma especificação, um software é desenvolvido e experimentado em condições de laboratório e, depois, falha no mundo real. Ao menos em engenharia sei que acontece.

@Rod100

Cara, eu não sei como é no mundo real porque eu não tenho nem dois meses de experiência, tô aprendendo com os desafios.

Mas uma coisa que me parece muito legal da programação, pelo menos dessa que tenho visto, é que você tem um feedback muito rápido, praticamente instantâneo.

Quando você pode errar à vontade e recebe feedback rápido, o mais importante não é a precisão, mas saber identificar os erros.

Em outras áreas, você demora pra receber feedback, às vezes ele depende de outra pessoa, enfim. E aí você precisa pensar muito antes de lançar a solução, pois não pode se dar ao luxo de errar muito.

Em programação, por outro lado, me parece que falhar rápido é mais inteligente que tentar acertar muito.