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 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

<?php <br>
/**

• @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!