Esborrar cada dos lletres consecutives iguals però una majúscula i l'altra minúscula X31002

En aquest exercici considerarem mots construits sobre l’alfabet {A,B,C,…,Z,a,b,c,…,z}, és a dir, totes les lletres majúscules i minúscules del codi ASCII, i les següents regles de reemplaçament sobre aquests mots:

• Aa→
• aA→
• Bb→
• bB→
• Cc→
• cC→
• …
• Zz→
• zZ→

Fixeu-vos que aquestes regles ens permeten agafar qualsevol submot, que sigui de mida dos i amb la mateixa lletra però una en majúscula i l’altra en minúscula, i reemplaçar-lo pel mot buit.

Donat un mot d’entrada w, voldrem donar com a sortida el mot resultant d’anar aplicant sobre w les regles anteriors tant com sigui possible.

Nota: el sistema de regles anterior és convergent, en el sentit que sempre acaba i que s’apliquin com s’apliquin les regles, i independentment de l’ordre i la posició, el resultat final quan ja no es pot aplicar cap més regla és el mateix.

Per exemple, si tenim com a entrada aBaCcAbBAabA, donarem com a sortida el mot buit, perquè a base d’aplicar les regles anteriors acabem eliminant tots els caràcters:

En canvi, si tenim com a entrada aBBAbb, el resultat és el mateix mot aBBAbb, doncs no es pot aplicar cap regla.

Observació: Podeu seguir l’enfoc que considereu oportú, i podeu utilitzar qualsevol de les estructures de dades presentades al curs (string, vector, stack, queue, list, map, set) de la manera que considereu oportuna. Noteu, però, que enfocaments diferents poden donar lloc a solucions més o menys eficients, i que superin només els jocs de proves públics o tots els jocs de proves, de manera que la nota acabarà depenent d’això.

Nota: Recordeu que podeu usar l’expressió (’a’ <= c and c <=’z’) per a comprovar si un char c guarda una lletra minúscula, i que la podeu transformar a majúscula amb char(c-’a’+’A’). Comprovar si c és majúscula i transformar-lo a minúscula és anàleg.

Entrada

L’entrada conté un nombre arbitrari de casos, un per línia. Cada cas consisteix en un string no buit sobre {A,B,C,…,Z,a,b,c,…,z}.

Sortida

Per a cada cas, escriviu en una línia el resultat d’aplicar les regles de reemplaçament tant com sigui possible.

Observació

Avaluació sobre 10 punts:

• Solució lenta: 5 punts.
• solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.