Construire une chaîne avec une limite de répétition

2182. Construire une chaîne avec une limite de répétition

Difficulté :Moyen

Sujets : Table de hachage, chaîne, gourmande, tas (file d'attente prioritaire), comptage

Vous recevez une chaîne s et un nombre entier repeatLimit. Construisez une nouvelle chaîne repeatLimitedString en utilisant les caractères de s tels qu'aucune lettre n'apparaisse plus derepeetLimit fois affilée. Vous n'êtes pas obligé d'utiliser tous les caractères de s.

Renvoyer la le plus grand lexicographiquementrepeetLimitedString possible.

Une chaîne a est lexicographiquement plus grande qu'une chaîne b si dans la première position où a et b diffèrent, la chaîne a a une lettre qui apparaît plus tard dans l'alphabet que la lettre correspondante dans b. Si les premiers caractères min(a.length, b.length) ne diffèrent pas, alors la chaîne la plus longue est la plus grande lexicographiquement.

Exemple 1 :

• Entrée : s = "cczazcc", repeatLimit = 3
• Sortie : "zzcccac"
• Explication : Nous utilisons tous les caractères de s pour construire la répétitionLimitedString "zzcccac".
  • La lettre « a » apparaît au maximum 1 fois de suite.
  • La lettre « c » apparaît au maximum 3 fois de suite.
  • La lettre 'z' apparaît au maximum 2 fois de suite.
  • Par conséquent, aucune lettre n'apparaît plus de répétitionLimit fois de suite et la chaîne est une chaîne de répétition limitée valide.
  • La chaîne est la chaîne de répétition lexicographiquement la plus grande possible, nous renvoyons donc "zzcccac".
  • Notez que la chaîne « zzcccca » est lexicographiquement plus grande mais que la lettre « c » apparaît plus de 3 fois de suite, ce n'est donc pas une chaîne de répétition limitée valide.

Exemple 2 :

• Entrée : s = "aababab", repeatLimit = 2
• Sortie : "bbabaa"
• Explication : Nous utilisons uniquement certains des caractères de s pour construire la répétitionLimitedString "bbabaa".
  • La lettre « a » apparaît au maximum 2 fois de suite.
  • La lettre 'b' apparaît au maximum 2 fois de suite.
  • Par conséquent, aucune lettre n'apparaît plus de répétitionLimit fois de suite et la chaîne est une chaîne de répétition limitée valide.
  • La chaîne est la chaîne de répétition lexicographique la plus grande possible, nous renvoyons donc "bbabaa".
  • Notez que la chaîne « bbabaaa » est lexicographiquement plus grande mais que la lettre « a » apparaît plus de 2 fois de suite, ce n'est donc pas une chaîne de répétition limitée valide.

Contraintes :

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

Indice :

1. Commencez à construire la chaîne par ordre décroissant de caractères.
2. Lorsque la limite de répétition est atteinte, choisissez le caractère le plus grand suivant.

Solution :

Nous utilisons une approche gourmande pour prioriser les caractères lexicographiquement plus grands tout en garantissant qu'aucun caractère ne dépasse la limite de répétition consécutivement. L'approche utilise une file d'attente prioritaire (tas max) pour traiter les caractères par ordre lexicographique décroissant et garantit qu'aucun caractère n'apparaît plus que le nombre de fois repeatLimit consécutivement.

Explication de la solution

1. Compter les caractères : comptez la fréquence de chaque caractère dans la chaîne s à l'aide d'un tableau.
2. Max Heap : utilisez un tas maximum (file d'attente prioritaire) pour trier et extraire les caractères par ordre lexicographique décroissant.
3. Construction gourmande :
   • Ajoutez le plus grand caractère disponible jusqu'à la limite de répétition.
   • Si la limite de répétition du caractère actuel est atteinte, passez au caractère le plus grand suivant, insérez-le une fois, puis réinsérez le premier caractère dans le tas pour une utilisation ultérieure.
4. Gestion des bords : Gérez correctement lorsqu'un personnage ne peut plus être utilisé.

Implémentons cette solution en PHP : 2182. Construire une chaîne avec une limite de répétition

<?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<p><strong>Compte de fréquence :</strong></p>

<ul>
<li>Parcourez la chaîne s pour compter les occurrences de chaque caractère.</li>
<li>Stockez la fréquence dans un tableau associatif $freq.</li>
</ul>
</li>
<li>
<p><strong>Trier par ordre décroissant :</strong></p>

<ul>
<li>Utilisez krsort() pour trier les caractères par ordre lexicographique <strong>décroissant</strong>.</li>
</ul>
</li>
<li>
<p><strong>Construisez le résultat :</strong></p>

<ul>
<li>Ajoutez continuellement le caractère lexicographiquement le plus grand ($char) à la chaîne de résultat.</li>
<li>Si un caractère atteint sa limite de répétition, arrêtez de l'ajouter temporairement.</li>
<li>Utilisez une file d'attente temporaire pour conserver les caractères qui ont encore un nombre restant mais qui sont temporairement ignorés.</li>
</ul>
</li>
<li>
<p><strong>Limite de répétition de la poignée :</strong></p>

<ul>
<li>Si le caractère actuel a atteint la limite de répétition, utilisez le caractère lexicographiquement le plus grand suivant de la file d'attente.</li>
<li>Réinsérez le caractère précédent dans la carte de fréquence pour continuer à le traiter plus tard.</li>
</ul>
</li>
<li>
<p><strong>Cas Edge :</strong></p>
<ul>
<li>Les personnages peuvent ne pas utiliser tout leur nombre au départ.</li>
<li>Après avoir traité un personnage de sauvegarde de la file d'attente, le personnage actuel reprend le traitement.</li>
</ul>
</li>
</ol>

<h3>
  
  
  <strong>Comment ça marche</strong>
</h3>

<ol>
<li>
<strong>Nombre de caractères</strong> : $freq garde une trace des occurrences de tous les caractères.</li>
<li>
<strong>Max Heap</strong> : SplPriorityQueue est utilisé comme un tas maximum, où les caractères sont hiérarchisés par leur valeur ASCII (ordre décroissant).</li>
<li>
<strong>Construction de cordes</strong> :

<ul>
<li>Si le caractère actuel a atteint sa limite de répétition, récupérez le caractère le plus grand suivant.</li>
<li>Utilisez une fois le caractère suivant le plus grand et réintégrez le caractère précédent dans le tas pour une utilisation future.</li>
</ul>
</li>
<li>
<strong>Résultat final</strong> : La chaîne résultante est la chaîne lexicographiquement la plus grande qui satisfait la contrainte repeatLimit.</li>
</ol>

<h3>
  
  
  <strong>Exemple de procédure pas à pas</strong>
</h3>

<p><strong>Entrée :</strong><br><br>
s = "cczazcc", répéterLimit = 3</p>

<p><strong>Étapes :</strong></p>

<ol>
<li><p>Compte de fréquence :<br><br>
['a' => 1, 'c' => 4, 'z' => 2]</p></li>
<li><p>Trier par ordre décroissant :<br><br>
['z' => 2, 'c' => 4, 'un' => 1]</p></li>
<li>
<p>Ajouter des caractères en respectant RepeatLimit :</p>

<ul>
<li>Ajouter 'z' → "zz" (z count = 0)</li>
<li>Ajouter 'c' 3 fois → "zzccc" (c count = 1)</li>
<li>Ajouter 'a' → "zzccca" (a count = 0)</li>
<li>Ajouter le « c » restant → « zzcccac »</li>
</ul>
</li>
</ol>

<p><strong>Sortie :</strong> "zzcccac"</p>

<h3>
  
  
  <strong>Complexité temporelle</strong>
</h3>

<ul>
<li>
<strong>Comptage de la fréquence des caractères</strong> : <em><strong>O(n)</strong></em>, où <em><strong>n</strong></em> est la longueur de la chaîne.</li>
<li>
<strong>Opérations sur le tas</strong> : <em><strong>O(26 log 26)</strong></em>, car le tas peut contenir jusqu'à 26 caractères.</li>
<li>
<strong>Complexité globale</strong> : <em><strong>O(n 26 log 26) ≈ O(n)</strong></em>.</li>
</ul>

<h3>
  
  
  <strong>Complexité spatiale</strong>
</h3>

<ul>
<li>
<em><strong>O(26)</strong></em> pour le tableau de fréquences.</li>
<li>
<em><strong>O(26)</strong></em> pour le tas.</li>
</ul>

<h3>
  
  
  <strong>Cas de test</strong>
</h3>



<pre class="brush:php;toolbar:false"><?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>

Cas Edge

1. s ne contient qu'un seul caractère unique (par exemple, "aaaaaaa", repeatLimit = 2) : la sortie n'inclura que le nombre de caractères autorisé consécutivement.
2. repeatLimit = 1 : la sortie alterne entre les caractères disponibles.
3. Tous les caractères de s sont uniques : la sortie est triée par ordre décroissant.

Cette implémentation fonctionne efficacement dans les limites des contraintes.

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!