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

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;
       
    }
};?

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)

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;        
    }
};?

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;       
    }
};

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

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;        
    }?

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;

    }
}?

#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;
}

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

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.