Supprimer des caractères pour créer une chaîne fantaisie

1957. Supprimer des caractères pour créer une chaîne fantaisie

Difficulté :Facile

Sujets : Chaîne

Une chaîne fantaisie est une chaîne dans laquelle aucun trois caractères consécutifs ne sont égaux.

Étant donné une chaîne s, supprimez le nombre minimum possible de caractères de s pour la rendre fantaisie.

Renvoyer la chaîne finale après la suppression. On peut montrer que la réponse sera toujours unique.

Exemple 1 :

• Entrée : s = "leeetcode"
• Sortie : "leetcode"
• Explication : Supprimez un « e » du premier groupe de « e » pour créer un « leetcode ». Il n'y a pas trois caractères consécutifs égaux, alors retournez "leetcode".

Exemple 2 :

• Entrée : s = "aaabaaaa"
• Sortie : "aabaa"
• Explication : Supprimez un « a » du premier groupe de « a » pour créer « aabaaaa ». Supprimez deux « a » du deuxième groupe de « a » pour créer « aabaa ». Il n'y a pas trois caractères consécutifs égaux, alors renvoyez "aabaa".

Exemple 3 :

• Entrée : s = "aab"
• Sortie : "aab"
• Explication : Il n'y a pas trois caractères consécutifs égaux, alors retournez "aab".

Contraintes :

• 1 <= s.length <= 10⁵
• s se compose uniquement de lettres anglaises minuscules.

Indice :

1. Quelle est la manière optimale de supprimer des caractères si trois caractères consécutifs ou plus sont égaux ?
2. Si trois caractères consécutifs ou plus sont égaux, conservez-en deux et supprimez le reste.

Solution :

Nous devons nous assurer qu'il n'y a pas trois caractères consécutifs identiques dans la chaîne finale. Nous allons parcourir la chaîne d'entrée et créer une nouvelle chaîne "fantaisie" en gardant une trace des deux caractères précédents. Si un troisième caractère consécutif correspond aux deux derniers, nous le sautons. Sinon, nous l'ajoutons à la sortie.

Implémentons cette solution en PHP : 1957. Supprimer des caractères pour créer une chaîne fantaisie

  
  
  Explication:




Initialiser les variables :



$result : Ceci stockera la chaîne finale "fantaisie".



Parcourir la chaîne :


Pour chaque personnage, vérifiez s'il forme un trio avec les deux derniers personnages du résultat.
Si c'est le cas, évitez de l'ajouter à $result.
Sinon, ajoutez-le à $result.



Renvoyer le résultat :

La chaîne $result ne contient désormais plus trois caractères identiques consécutifs.





  
  
  Analyse de complexité




Complexité temporelle : O(n), où n est la longueur de la chaîne d'entrée, car nous traiter chaque personnage une fois.

Complexité spatiale : O(n), pour stocker la chaîne de sortie.


Cette solution répond efficacement aux contraintes et garantit que la chaîne finale ne comporte pas trois caractères identiques consécutifs.

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!