Prenez K de chaque personnage de gauche et de droite

2516. Prenez K de chaque personnage de gauche et de droite

Difficulté :Moyen

Sujets : Table de hachage, chaîne, fenêtre coulissante

Vous recevez une chaîne s composée des caractères « a », « b » et « c » et d'un entier non négatif k. Chaque minute, vous pouvez prendre soit le caractère le plus à gauche de s, soit le caractère le plus à droite de s.

Renvoyer le nombre minimum de minutes nécessaires pour que vous preniez au moins k de chaque caractère, ou renvoie -1 s'il n'est pas possible de prendre k de chacun personnage.

Exemple 1 :

• Entrée : s = "aabaaaacaabc", k = 2
• Sortie : 8
• Explication : Prenez trois caractères à gauche de s. Vous avez maintenant deux caractères « a » et un caractère « b ».
  • Prenez cinq caractères à droite de s. Vous disposez maintenant de quatre caractères « a », deux caractères « b » et deux caractères « c ».
  • Un total de 3 5 = 8 minutes est nécessaire.
  • Il peut être prouvé que 8 est le nombre minimum de minutes nécessaires.

Exemple 2 :

• Entrée : s = "a", k = 1
• Sortie : -1
• Explication : Il n'est pas possible de prendre un 'b' ou un 'c' donc retournez -1.

Contraintes :

• 1 <= s.length <= 10⁵
• s se compose uniquement des lettres « a », « b » et « c ».
• 0 <= k <= s.length

Indice :

1. Commencez par compter la fréquence de chaque caractère et vérifiez si c'est possible.
2. Si vous prenez x caractères du côté gauche, quel est le nombre minimum de caractères que vous devez prendre du côté droit ? Trouvez ceci pour toutes les valeurs de x dans la plage 0 ≤ x ≤ s.length.
3. Utilisez une approche à deux points pour éviter de calculer plusieurs fois les mêmes informations.

Solution :

Nous pouvons utiliser une technique de fenêtre coulissante avec deux pointeurs pour trouver le nombre minimum de minutes nécessaires pour prendre au moins k de chaque caractère (« a », « b », « c ») à gauche et à droite du chaîne.

Répartition du problème :

• On nous donne une chaîne s contenant uniquement « a », « b » et « c ».
• Nous devons prendre au moins k occurrences de chaque caractère, soit à partir des caractères les plus à gauche, soit à l'extrême droite de la chaîne.
• Nous devons déterminer le nombre minimum de minutes nécessaires pour y parvenir ou renvoyer -1 si c'est impossible.

Approche:

1. Vérifications initiales :

   • Si k == 0, on peut retourner directement 0 puisqu'aucun caractère n'est requis.
   • Si k dépasse le nombre d'occurrences d'un caractère dans la chaîne, renvoie immédiatement -1.

2. Compte de fréquence :

   • Nous devons compter combien de fois « a », « b » et « c » apparaissent dans la chaîne s pour nous assurer qu'il est même possible de rassembler k de chaque caractère.

3. Technique de la fenêtre coulissante :

   • Utilisez une approche par fenêtre coulissante avec deux pointeurs (gauche et droite).
   • Maintenez deux pointeurs et faites-les glisser des deux extrémités de la chaîne pour rassembler les caractères requis.
   • Pour chaque nombre de caractères pris à gauche, calculez le nombre minimum de caractères qui doivent être pris à droite pour satisfaire à l'exigence.

4. Optimisation :

   • Au lieu de recalculer le nombre de caractères à plusieurs reprises pour chaque fenêtre, nous pouvons suivre le nombre de caractères à mesure que nous agrandissons ou réduisons la fenêtre.

Implémentons cette solution en PHP : 2516. Prenez K de chaque personnage de gauche à droite

  
  
  Explication:




Configuration initiale :


Nous comptons les occurrences de « a », « b » et « c » dans la chaîne entière pour nous assurer qu'il est possible de rassembler au moins k de chaque caractère.
Si un nombre de caractères est inférieur à k, renvoie -1.



Fenêtre coulissante :


Nous utilisons deux pointeurs (gauche et droite) pour créer une fenêtre coulissante des deux extrémités.
On agrandit la fenêtre en déplaçant le pointeur droit et on incrémente le nombre de caractères rencontrés.
Une fois que nous avons au moins k de chaque caractère dans la fenêtre actuelle, nous essayons de réduire la fenêtre de gauche pour minimiser le nombre de minutes (caractères pris).



Réduire le temps :


Nous suivons le nombre minimum de minutes requises en comparant la taille de la fenêtre à chaque fois que nous collectons k caractères de tous types.





  
  
  Complexité temporelle :



Le comptage des caractères prend initialement O(n).
L'opération de fenêtre coulissante prend O(n), car les pointeurs gauche et droit se déplacent une fois sur la chaîne.
La complexité temporelle globale est O(n).



  
  
  Cas extrêmes :



Si k == 0, renvoie 0.
S'il est impossible de prendre k de chaque caractère, retournez -1.


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!