Acertijos de programación: Encontrar la primera letra repetida

Sigo avanzando con esta nueva serie de apuntes, pensando en algunos acertijos de programación.

En este caso voy a revisar un acertijo que se conoce entre otros nombres por el “problema de encontrar la primera letra repetida dentro de un string”.

Ya antes estuve haciendo otro acertijo, que trataba de encontrar dos cifras que den un resultado específico dentro de un array de datos.

Cómo siempre, recuerden que estoy dando mi perspectiva de principiante en el tema. Estoy escribiendo para motivarme a aprender más, por eso me interesa escuchar tu opinión sobre el tema.

Sin más introducción…

El problema

El acertijo dice lo siguiente.

Dado un string presentado de la siguiente forma:

palabra = “vocabulario”

Crear una función que diga cuál es la primera letra en repetirse dentro del string.

Los materiales

En esta oportunidad tenemos un string, y necesitamos encontrar la primera letra que se repite.

Lo que tenemos para trabajar es:

Un string:

Se trata de una secuencia de caracteres encerrado entre un par de comillas. Una palabra o una fase por ejemplo. También puede haber números, pero no se puede realizar operaciones matemáticas con esas cifras. Se interpretan como un carácter más.

La forma en que se presenta el string puede variar entre lenguaje y lenguaje. Por ejemplo, en Python un string guardado en una variable se aparece de este modo:

ejemplo = “hola123”

Guardando el string entre comillas. En la mayoría de los casos, usarlo sin comillas va a dar un error de sintaxis.

Un índice:

Se trata de la posición de un dato, en este caso la posición de cada carácter dentro de un string.

Gracias al índice puedo saber en que “lugar” se encuentra cada parte respecto a las demás letras. En la mayoría de los casos, a menos que el lenguaje avise lo contrario, el indice comienza en cero.

Por ejemplo en el caso del string “abeja”:

a b e j a
0 1 2 3 4

Se puede notar que la “a” tiene un índice “0” mientras que la “b” siguiente tiene un índice de 1. Y así en adelante.

Esto es importante porque en este acertijo necesito acceder a cada parte del string individualmente.

Una función:

Necesito revisar el string por medio de una función. Esta función tiene que entregar por respuesta la primera letra repetida.

Un “método incorporado”

En algunos lenguajes, por ejemplo en Python, voy a disponer de librerías que ya tienen herramientas para resolver algunos problemas.

A veces esas librerías son externas y necesitan ser instaladas independientemente.

Otras veces esas librerías pueden ser llamadas directamente porque son parte de la instalación básica de Python y se conocen como “built-in”.

Un “set”

Un set es un conjunto de elementos únicos desordenados. Pueden ser cambiados luego de ser creados.

Vamos a usarlos en este caso para guardar los caracteres que vamos encontrando al revisar el script.

Un diccionario

Es algo que existe en Python, aunque existen tipos de datos similares en otros lenguajes de programación.

Se trata de asociar una entrada con un valor, donde cada parte se encuentra “mapeada” con su contraparte. Por ejemplo en nuestro caso, una entrada “a” (la letra a) se encuentra asociada con el valor 1 (el número de veces que aparece dentro del string).

Resolución en Python

Del mismo modo que dije antes, una de las primeras formas que tenemos de resolver este problema es utilizando uno de los métodos incorporados de Python.

Este método en particular se llama “count ()” que cuanta cada vez que aparece un carácter en un string.

El código es el siguiente:

def encontrar_letra(palabra):
    palabra = palabra.lower() # convertir string en minúscula
    for i in range(len(palabra)):
        if palabra.count(palabra[i]) > 1:
            print("La primera letra repetida es:", palabra[i])
            break
    else:
         print("Sin letra repetida")
    

palabra = "Vocabulario"
encontrar_letra(palabra)

Y el resultado de este código es:

La primera letra repetida es: o

Otra cosa que estamos haciendo en ese ejemplo es convertir a todo el string en minúscula, porque nos interesa encontrar la primera letra repetida sin importar si es minúscula o mayúscula. Pero si el problema especificara lo contrario, simplemente podríamos retirar la linea “palabra = palabra.lower()”.

Aunque en este caso, la respuesta nos dice que la primera letra repetida es la letra “o”. Aunque esa letra si aparece repetida, se puede decir que en realidad la primera en repetirse es la “a”. La “o” aparece antes en el indice, pero la “a” tiene su repetición antes.

Tal vez estoy leyendo demasiado en el problema, pero podemos solucionar esto por medio de un set.

El código de Python aparece ahora de esta forma:

def encontrar_letra(palabra):
    palabra = palabra.lower()
    guardar = set()
    for letra in palabra:
        if letra in guardar:
            print("La primera letra repetida es:", letra)
            break
        guardar.add(letra)
    else:
        print("Sin letras repetidas")


palabra = "Vocabulario"
encontrar_letra(palabra)

Y el resultado es el siguiente:

La primera letra repetida es: a

Lo que ocurre es que al usar la linea “guardar.add(letra)” vamos llevando un inventario en un set de los caracteres que ya aparecieron. Eso hace que la “a” aparezca como repetida antes, porque su coincidencia aparece antes que la de la letra “o”.

def encontrar_letra(palabra):
    guardados = {}
    for caracter in palabra:
        if caracter in guardados:
            print("La primera letra repetida es:", caracter)
            return caracter
        else:
            guardados[caracter] = 1
    print("No hay letra repetida")
    

palabra = "vocabulario"
encontrar_letra(palabra)

Y nos da por respuesta:

La primera letra repetida es: a

Resolución en Bash

La respuesta en bash, como en el acertijo anterior, otra vez se trata de un loop que revisa cada instancia del string.

Aunque como en el caso de Python, también estamos convirtiendo el string a todo minúsculas para volver un poco más complejo el problema.

El código queda de la siguiente forma:

#!/bin/bash

function encontrar_letra {
    palabra=$(echo $1 | tr '[:upper:]' '[:lower:]')
    len=${#palabra}
    for ((i=0; i<len; i++)); do
        for ((j=i+1; j<len; j++)); do
            if [[ "${palabra:$i:1}" == "${palabra:$j:1}" ]]; then
                echo "La primera letra repetida es: ${palabra:$i:1}"
                return
            fi
        done
    done
    echo "No se encontró ninguna letra repetida."
}

palabra="Vocabulario"
encontrar_letra $palabra

Y nos dice que el resultado es:

La primera letra repetida es: o

Otra vez, el resultado de la primera letra repetida es “o”. Lo que es cierto, es la primera letra que al aparecer luego tiene una repetición.

Pero si quiero modificarlo para que la primera letra que tiene un repetido sea “a”, la letra que tiene su repetido más cerca, puedo hacer:

#!/bin/bash

function encontrar_letra {
    palabra=$(echo $1 | tr '[:upper:]' '[:lower:]')
    len=${#palabra}
    guardar=()
    for ((i=0; i<len; i++)); do
        caracter="${palabra:$i:1}"
        if [[ " ${guardar[*]} " == *" $caracter "* ]]; then
            echo "La primera letra repetida es: $caracter"
            return
        fi
        guardar+=("$caracter")
    done
    echo "No se encontró ninguna letra repetida."
}

palabra="vocabulario"
encontrar_letra $palabra

Y la respuesta es:

La primera letra repetida es: a

Aunque en bash no estamos creando un set, si estamos generan un nuevo string que guarde las letras en el orden que aparecen. Esto nos ayuda a modificar el código, para que la primera letra repetida sea realmente “a”.

Conclusión

Con esto termina el apunte sobre el acertijo que nos pide encontrar la primera letra repetida en un string.

Si encontrás algún error en el material, por favor avisame para que pueda corregirlo. Y también me interesa conocer que otras soluciones encontrás para este problema, podes encontrar mi correo electrónico en la sección de contacto.

La seguimos en el próximo apunte.