Longueur minimale de chaîne après les opérations

3223. Longueur minimale de la chaîne après les opérations

Difficulté :Moyen

Sujets : Table de hachage, chaîne, comptage

Vous recevez une chaîne s.

Vous pouvez effectuer le processus suivant n'importe quel nombre de fois :

• Choisissez un index i dans la chaîne tel qu'il y ait au moins un caractère à gauche de l'index i qui soit égal à s[i], et au moins un caractère à droite qui est également égal à s[i].
• Supprimer le caractère le plus proche à gauche de l'index i qui est égal à s[i].
• Supprimer le caractère le plus proche à droite de l'index i qui est égal à s[i].

Renvoyer la longueur minimale des chaînes finales que vous pouvez atteindre.

Exemple 1 :

• Entrée : s = "abaacbcbb"
• Sortie : 5
• Explication : Nous effectuons les opérations suivantes :
  • Choisissez l'index 2, puis supprimez les caractères aux indices 0 et 3. La chaîne résultante est s = "bacbcbb".
  • Choisissez l'index 3, puis supprimez les caractères aux indices 0 et 5. La chaîne résultante est s = "acbcb".

Exemple 2 :

• Entrée : s = "aa"
• Sortie : 2
• Explication : Nous ne pouvons effectuer aucune opération, nous renvoyons donc la longueur de la chaîne d'origine.

Contraintes :

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

Indice :

1. Seule la fréquence de chaque caractère compte pour trouver la réponse finale.
2. Si un personnage apparaît moins de 3 fois, nous ne pouvons effectuer aucun processus avec lui.
3. Supposons qu'il y ait un caractère qui apparaît au moins 3 fois dans la chaîne, nous pouvons supprimer à plusieurs reprises deux de ces caractères jusqu'à ce qu'il en reste au plus 2 occurrences.

Solution :

Nous devons nous concentrer sur la fréquence de chaque caractère de la chaîne. Voici l’approche pour le résoudre :

Approche:

1. Compter les fréquences des caractères :

   • Utilisez un tableau de fréquence pour compter combien de fois chaque caractère apparaît dans la chaîne.

2. Réduire les caractères avec une fréquence >= 3 :

   • Si un caractère apparaît 3 fois ou plus, nous pouvons en supprimer deux à plusieurs reprises jusqu'à ce qu'il ne reste plus que 2 occurrences.

3. Calculer la longueur minimale :

   • Résumez le nombre restant de tous les caractères après avoir réduit les fréquences.

Implémentons cette solution en PHP : 3223. Longueur minimale de la chaîne après les opérations


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

// Example 1
$s1 = "abaacbcbb";
echo "Input: $s1\n";
echo "Output: " . minimumLength($s1) . "\n";

// Example 2
$s2 = "aa";
echo "Input: $s2\n";
echo "Output: " . minimumLength($s2) . "\n";
?>

Explication:

1. Compte de fréquence :

   • Parcourez la chaîne et pour chaque caractère, incrémentez son nombre dans le tableau $fréquence.

2. Réduction des Caractères:

   • Pour chaque caractère du tableau $fréquence, vérifiez si son nombre est de 3 ou plus. Si c'est le cas, réduisez-le à 2 au maximum.

3. Calculer le résultat :

   • Sommez les valeurs du tableau $fréquence pour obtenir la longueur minimale possible de la chaîne.

Exemple de procédure pas à pas :

Exemple 1 :

• Entrée : s = "abaacbcbb"
• Fréquences : ['a' => 3, 'b' => 4, 'c' => 2]
• Après réduction :
  • 'a' => 2 (au lieu de 3),
  • 'b' => 2 (au lieu de 4),
  • 'c' => 2 (aucune réduction nécessaire).
• Longueur minimale : 2 2 2 = 6.

Exemple 2 :

• Entrée : s = "aa"
• Fréquences : ['a' => 2]
• Aucune réduction nécessaire puisqu'aucun personnage n'a une fréquence de 3 ou plus.
• Longueur minimale : 2.

Complexité:

1. Complexité temporelle :

   • Fréquences de comptage : O(n), où n est la longueur de la chaîne.
   • Réduction : O(1) (temps constant, car il n'y a que 26 lettres minuscules).
   • Fréquences de sommation : O(1).
   • Global : O(n).

2. Complexité spatiale :

   • O(1), puisque le tableau de fréquences a au plus 26 entrées.

Cette solution est efficace et fonctionne bien dans les contraintes du problème.

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!