Anagrams

Enunciado do problema

Dadas duas strings, a e b, que podem ou não ter o mesmo comprimento, determine o número mínimo de exclusões de caracteres necessárias para tornar a e b anagramas.

Qualquer caractere pode ser excluído de qualquer uma das strings.

Questões para fazer

Caracteres na string são apenas minúsculos? Sim

Podem existir caracteres especiais na string? Não

Solução

A solução é bem direta. Sabendo que o caractere é um número de 0 a 255, crie um vetor para contar a frequência dos caracteres da primeira string. Agora você passará pelo segundo array e removerá o caractere do vetor que conta a freqüência. Faça um loop pelo vetor de frequência e some o valor absoluto de cada índice a uma variável de resultado.

Como os caracteres são apenas minúsculos, um vetor de 26 posições poderia ser utilizado ao invés de um de 255 fazendo a subtração do valor ASCII ‘a’ de cada caractere.

int getMinimumDeletionsToAnagram(string s1, string s2){
  vector<int> count(256,0);
  int result =0;
  for(auto c:s1){
    count[c-'a']++;
  }

  for(auto c:s2){
    count[c-'a']--;
  }

  for(auto val : count){
    result+=abs(val);
  }

  return result;
}

Complexidade do Tempo: O(n)

Complexidade do espaço: O(1)

question from HackerRank