Longueur minimale de la chaîne après la suppression des sous-chaînes

2696. Longueur minimale de la chaîne après la suppression des sous-chaînes

Difficulté :Facile

Sujets : Chaîne, Pile, Simulation

Vous recevez une chaîne s composée uniquement de majuscules lettres anglaises.

Vous pouvez appliquer certaines opérations à cette chaîne où, en une seule opération, vous pouvez supprimer toute occurrence de l'une des sous-chaînes "AB" ou "CD" de s.

Renvoyer la longueur minimale possible de la chaîne résultante que vous pouvez obtenir.

Notez que la chaîne se concatène après avoir supprimé la sous-chaîne et pourrait produire de nouvelles sous-chaînes "AB" ou "CD".

Exemple 1 :

• Entrée : s = "ABFCACDB"
• Sortie : 2
• Explication : On peut faire les opérations suivantes :
  • Supprimez la sous-chaîne "ABFCACDB", donc s = "FCACDB".
  • Supprimez la sous-chaîne "FCACDB", donc s = "FCAB".
  • Supprimez la sous-chaîne "FCAB", donc s = "FC".
  • La longueur résultante de la chaîne est donc de 2.
  • On peut montrer que c'est la longueur minimale que l'on peut obtenir.

Exemple 2 :

• Entrée : s = "ACBBD"
• Sortie : 5
• Explication : Nous ne pouvons effectuer aucune opération sur la chaîne donc la longueur reste la même.

Contraintes :

• 1 <= s.length <= 100
• s se compose uniquement de lettres anglaises majuscules.

Indice :

1. Pouvons-nous utiliser la force brute pour résoudre le problème ?
2. Parcourez la chaîne à plusieurs reprises pour rechercher et supprimer les sous-chaînes « AB » et « CD » jusqu'à ce qu'il n'y ait plus d'occurrences.

Solution :

Nous utiliserons une pile pour gérer la suppression des sous-chaînes "AB" et "CD". L'approche par pile garantit que nous supprimons efficacement ces sous-chaînes au fur et à mesure qu'elles se produisent lors du parcours de la chaîne.

Approche:

1. Utiliser une pile :
   • Parcourez la chaîne caractère par caractère.
   • Poussez chaque personnage sur la pile.
   • Si les deux premiers caractères de la pile forment la sous-chaîne "AB" ou "CD", retirez ces deux caractères de la pile (supprimez-les).
   • Continuez ce processus pour tous les caractères de la chaîne d'entrée.
2. Chaîne finale :
   • A la fin du parcours, la pile contiendra la chaîne réduite.
   • La longueur minimale possible sera la taille de la pile.

Implémentons cette solution en PHP : 2696. Longueur minimale de la chaîne après la suppression des sous-chaînes

/**


@param String $s
@return Integer
/


function minLengthAfterRemovals($s) {
...
...
...
/*


go to ./solution.php
*/

}



// Example usage:

echo minLengthAfterRemovals("ABFCACDB"); // Output: 2

echo "\n";

echo minLengthAfterRemovals("ACBBD");    // Output: 5

?>





  

  

  Explication :




On initialise une pile vide ($stack).
Parcourez chaque caractère de la chaîne s.
Vérifiez le caractère supérieur de la pile :


Si le caractère supérieur et le caractère actuel forment les sous-chaînes "AB" ou "CD", nous supprimons le caractère supérieur à l'aide de array_pop.
Sinon, poussez le caractère actuel sur la pile.





La pile contiendra les caractères qui restent après toutes les suppressions possibles.

Enfin, count($stack) donne la longueur de la chaîne résultante.




  
  
  Complexité:




Complexité temporelle : O(n), où n est la longueur de la chaîne. Chaque caractère est traité au maximum deux fois (une fois poussé, une fois sauté).

Complexité spatiale : O(n) pour la pile, dans le pire des cas où aucun retrait n'est possible.


Cette solution minimise efficacement la chaîne en supprimant toutes les occurrences possibles de « AB » et « CD » jusqu'à ce qu'il n'y en ait plus.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!