Lógica del algoritmo
La lógica es la siguiente:
- Se prepara una variable (que llama
actual
) para contener la sub-cadena ordenada que se ha encontrado de momento. Una subcadena ordenada contiene sólo elementos que se hallan en orden alfabético, es decir, que cada elemento de la cadena es "mayor o igual" que el anterior (alfabéticamente). Una subcadena ordenada se termina tan pronto como aparezca una letra que es menor (alfabéticamente) que la anterior. Por ejemplo, si de momento llevamos encontradas las letras "mrs" esa es una subcadena ordenada. Si la letra siguiente es por ejemplo "t" se añadiría a esa subcadena, pues "t" es mayor (alfabéticamente) que "s". Pero si se encuentra "f", entonces la subcadena ordenada que llevábamos hasta ese punto se da por terminada y se comienza una nueva que de momento sería "f".
- Cada letra que se vaya procesando de la cadena de entrada o bien se añade a la subcadena
actual
(si es menor o igual que su última letra), o bien da comienzo a una nueva subcadena.
- A la vez, se tiene otra variable (llamada
larga
) para contener la subcadena más larga encontrada hasta el momento. Esta variable se actualiza cada vez que la subcadena contenida en actual
es mayor (en longitud) que la que había en larga
.
Una vez tenemos claro (más o menos) el funcionamiento del algoritmo, la forma de comprenderlo de verdad es ejecutarlo "paso a paso", es decir, seguir instrucción a instrucción lo que va ocurriendo con cada variable.
Ejecución paso a paso
Para este tipo de ejecuciones paso a paso un depurador es una herramienta muy útil. Visual Studio Code es un editor que se integra bien con Python y que tiene un depurador que te permite ejecutar paso a paso los programas e inspeccionar las variables. Si no tienes acceso a él o no sabes cómo configurarlo y usarlo, también puedes utilizar algún servicio on-line como pythontutor
Pero incluso sin nada de eso puedes ejecutar paso a paso el programa "mentalmente" y si en algún momento te pierdes, insertar en tu código algún print()
que te muestre los valores de las variables según va pasando por las iteraciones.
Intentemos ejecutar paso a paso el programa "mentalmente" con la entrada s = "azcbobobegghakl"
- La sub-cadena ordenada encontrada hasta el momento consiste solo en la primera letra
s[0]
que es "a"
.
- La sub-cadena más larga encontrada hasta el momento es obviamente esa misma letra.
- Iteramos por las restantes letras una a una (
s[1:]
significa todas las letras desde la 1 en adelante, pues la 0 ya la hemos procesado). En cada iteración la variable c
tomará el valor de una de las letras.
Primera iteración del bucle:
- En la primera iteración la letra
c
tomará el valor de s[1]
, que es "z".
- Se compara esta letra con la última que teníamos en
actual
(el subíndice -1 significa en python el último elemento de una cadena o lista). Por tanto estamos comparando "a" con "z".
- Ya que es mayor, se añade a
actual
que pasa ahora a valer "az"
- Ya que la longitud de
actual
es mayor que la longitud de larga
, significa que hemos encontrado una cadena más larga que la más larga hasta ahora. De modo que actualizamos larga
para que sea igual a actual
. Ahora larga
vale también "az"
Pasemos a la siguiente iteración del bucle, en la que c
vale "c" (la siguiente letra de la cadena).
- Se compara con la última letra de
actual
, que era "z".
- Como no es mayor o igual, esto dará comienzo a una nueva subcadena. El valor de
actual
pasa a ser "c".
- Como la longitud de
actual
no es mayor que la longitud de larga
, no cambiamos el valor de esta última. larga
sigue valiendo "ac", que es la subcadena ordenada más larga encontrada hasta este momento.
En la siguiente iteración encontramos "b" que al ser menor que "c" da comienzo a una nueva subcadena. actual
pasa a valer "c".
No voy a continuar. Puedes seguir tú ejecutando "paso a paso" (es un buen ejercicio) y descubrir cómo al llegar a "beggh" y ser cada una de estas letras mayor que la anterior, se van actualizando las variables actual
y también larga
. Después de esto viene una "a" que "reseteará" la variable actual
(por ser menor que la última letra) al valor "a". Y después vienen "k" y "l" que se irán añadiendo a actual
, que llega a tomar el valor "akl", pero que al tener sólo tres letras (menos que las cinco letras que contiene larga
) no causan que esta última se actualice.
Al salir del bucle tendrás en actual
el valor "akl" (la última subcadena ordenada encontrada) y en larga
"beggh" (la subcadena ordenada más larga encontrada).
"Depuración" mediante print
Si te has perdido con esta explicación, prueba a insertar prints
en el código como los siguientes:
s = "azcbobobegghakl"
larga = s[0]
actual = s[0]
for c in s[1:]:
print("Letra que se está procesando:", c)
print("Letra anterior:", actual[-1])
if c >= actual[-1]:
actual += c
if len(actual) > len(larga):
larga = actual
else:
actual = c
print("actual=", actual)
print("larga=", larga)
print("La subcadena más larga en orden alfabético es:", larga)