Letra repetida

24 de diciembre, 2024

Supongamos que te dan una cadena de texto, en ella hay letras que aparecen solo una vez, salvo una que aparece dos veces; tu tarea es mostrar la letra repetida.

Por ejemplo:

Input: “aba”, resultado: “a”
Input: “zz”, resultado: “z”

Letras en minúsculas, del rango entre [2..27]

Análisis 1/3

Debemos contar la frecuencia de cada caracter para luego conocer cual de ellos tiene la frecuencia más alta, como nos han dicho que solo se repetirá una vez con que sepamos el valor máximo de frecuencia será suficiente.

function solution(string $s) 
{
   $charFrequencies = [];
   $inputArray = str_split($s);
   $inputLength = count($inputArray);

   for ($i = 0; $i < $inputLength; $i++) {
      $char = $inputArray[$i];
      if (!isset($charFrequencies[$char])) {
        $charFrequencies[$char] = 0;
      }
      $charFrequencies[$char]++;
   }

   return $charFrequencies;
}

Test: Probemos lo anterior

Mediante una prueba unitaria probemos el código creado anteriormente:

public function testCountFrequencies() : void
{
  $input = "aba";
  $expected = ['a' => 2, 'b' => 1];
  $actual = solution($input);

  $this->assertSame($expected, $actual, "The frequency count for '{$input}' is incorrect.");
}

Análisis 2/3

Nuestra tarea ahora es encontrar el caracter con mayor frecuencia, o sea que estamos en búsqueda de aquel 2, Modificaremos parcialmente nuestro código y test solo para centrarnos en nuestro nuevo objetivo:

function solution(string $s): int 
{

   //...

   $maxFrequency = 0;
   foreach ($charFrequencies as $freq) {
     if ( $freq > $maxFrequency) {
       $maxFrequency = $freq;
     }
   }

   return $maxFrequency;

}

El test de lo anterior

public function testReturnsMaxFrequency() : void
{
    $input = "aba";
    $expected = 2;
    $actual = solution($input);

    $this->assertSame($expected, $actual, "The expected value for '{$input}' is incorrect.");
}

Análisis 3/3

Ya tenemos nuestro arreglo de frecuencia, ya sabemos el valor máximo de frecuencia, ahora solo nos queda unir estas dos partes y devolver el caracter asociado a la frecuencia máxima:

function solution(string $s): string 
{

  //...

  $result = '';
  foreach ($charFrequencies as $char => $freq) {
    if ($freq === $maxFrequency) {
      $result = $char;
      break;
    }
  }

  return $result;

}

Vamos a testear lo anterior

Este será nuestro test final:

public function testReturnsTheRepeatedChar() : void
{
  $input = "aba";
  $expected = "a";
  $actual = solution($input);

  $this->assertSame($expected, $actual, "The expected value for '{$input}' is incorrect.");
}

Refactorizar

Listo, problema resuelto… pero espera un segundo; esos son demasiados bucles (un bucle for y dos bucles foreach) ¿no lo crees? Hagamos esto de una forma más limpia y eficiente —y— lo más importante… sin tocar en lo absoluto nuestro test.

function solution(string $s): string
{
  /**
   * str_split: toma la cadena $s y la convierte en un array
   *
   * array_count_values: toma un array y devuelve un array asociativo donde las
   * claves son los valores únicos del array original y los valores son la
   * frecuencia con la que aparecen esos valores.
   */
  $charFrequencies = array_count_values(str_split($s));

  /**
   * max: toma un array y devuelve el valor máximo de ese array
   */
  $maxFrequency = max($charFrequencies);

  /**
   * array_filter: filtra un array usando una función callback. Para este 
   * caso la función callback es una función anónima (arrow function) que
   * devolverá true si la frecuencia $freq es igual a $maxFrequency
   * 
   * key: devuelve la clave del primer elemento de un array
   */
  return key(array_filter($charFrequencies, fn($freq) => $freq === $maxFrequency));
}

algoritmo codigo php

←más añejo más fresco→