Enunciado del problema 1071. Máximo común divisor de cadenas

Para dos cadenas s y t, decimos "t divide a s" si y sólo si s = t t t ... t t (es decir, t está concatenado consigo mismo una o más veces).

Dadas dos cadenas str1 y str2, devuelve la cadena más grande x tal que x divide tanto str1 como str2.

Mi proceso de pensamiento

Aunque el leetcode lo marcó como un problema fácil, debo admitir que me resultó difícil encontrar una solución de inmediato.

Permítanme revisar los casos de prueba proporcionados por leetcode y repasarlos para explicar mi confusión.

Casos de prueba

Entrada: str1 = "ABCABC", str2 = "ABC"
Salida: "ABC"

Entrada: str1 = "ABABAB", str2 = "ABAB"
Salida: "AB"

A partir del enunciado del problema y del caso de prueba 1, determiné que necesitamos generar la cadena más grande ("ABC") concatenando la cual podemos obtener ambas cadenas. (cadena predeterminada "ABC" === str2 y "ABC" "ABC" === str1).

Sin embargo, al observar el caso de prueba 2, rápidamente me di cuenta de que mi comprensión no era correcta, ya que de acuerdo con eso debería generar "ABAB", ya que esa es la cadena más larga con la que puedo crear ambas cadenas. Pero salté al código y comencé a idear una solución. (¿Error de novato?)

Lo que falló/tuvo éxito

Solo pude idear una solución donde:

1. encuentra el MCD de dos cadenas.
2. iterar desde la longitud de la cadena más pequeña hasta GCD
3. tomar una subcadena desde la cadena más pequeña al valor de iteración actual.
4. si ambas cadenas contienen esa subcadena, devuelve esa subcadena como respuesta.
5. si no se encuentra ninguna cadena, devuelva "".

Como puede ver, mi solución falló para las cadenas donde str1 contiene str2 pero también contiene algunos otros caracteres adicionales. violando el requisito de que s = t t ... t t.

Tuve que recurrir a la solución de neetcode en busca de ayuda. Entendí rápidamente mis problemas:

1. Estaba encontrando el MCD de la longitud de la cadena, NO la cadena en sí. Necesito encontrar una cadena donde, repitiendo esas cadenas, pueda crear ambas cadenas sin ningún carácter restante.

2. Me di cuenta de por qué "ABAB" no puede ser la respuesta para el caso de prueba 2:

• Necesitamos encontrar x tal que divida ambas cadenas por igual. entonces, tomando "ABAB" como cadena puedes crear str2 completamente, pero para str1 terminas con "ABABABAB". Terminas con 2 "AB" sobrantes y no puedes decir que creaste str1 completamente combinando x.

• "ABAB" longitud 4 y "ABABAB" longitud 6. El MCD de las 2 cadenas = 2. Por lo tanto, la salida debe ser una cadena de longitud 2.

Producción

Complejidad del tiempo y el espacio

Complejidad del tiempo: En el peor de los casos, iteramos sobre Min(str1,str2) y necesitamos recrear str1 y str2 para que sean (str1.length str2.length), por lo que la complejidad del tiempo general será O(min(str1,str2) * (str1.length str2.length))

Complejidad del espacio: O(1) ya que no necesitamos ningún espacio adicional.