Sous-séquences alindromiques de longueur uniques

1930. Sous-séquences palindromiques uniques de longueur 3

Difficulté :Moyen

Sujets : Table de hachage, chaîne, manipulation de bits, somme de préfixes

Étant donné une chaîne s, renvoie le nombre de palindromes uniques de longueur trois qui sont une sous-séquence de s.

Notez que même s'il existe plusieurs façons d'obtenir la même sous-séquence, elle n'est toujours comptée qu'une seule fois.

Un palindrome est une chaîne qui lit la même chose vers l'avant et vers l'arrière.

Une sous-séquence d'une chaîne est une nouvelle chaîne générée à partir de la chaîne d'origine avec certains caractères (peut n'en être aucun) supprimés sans changer l'ordre relatif des caractères restants.

• Par exemple, "ace" est une sous-séquence de "abcde".

Exemple 1 :

• Entrée : s = "aabca"
• Sortie : 3
• Explication : Les 3 sous-séquences palindromiques de longueur 3 sont :
  • "aba" (sous-séquence de "aabca")
  • "aaa" (sous-séquence de "aabca")
  • "aca" (sous-séquence de "aabca")

Exemple 2 :

• Entrée : s = "adc"
• Sortie : 0
• Explication : Il n'y a pas de sous-séquences palindromiques de longueur 3 dans "adc".

Exemple 3 :

• Entrée : s = "bbcbaba"
• Sortie : 4
• Explication : Les 4 sous-séquences palindromiques de longueur 3 sont :
  • "bbb" (sous-séquence de "bbcbaba")
  • "bcb" (sous-séquence de "bbcbaba")
  • "bab" (sous-séquence de "bbcbaba")
  • "aba" (sous-séquence de "bbcbaba")

Contraintes :

• 3 5
• s se compose uniquement de lettres anglaises minuscules.

Indice :

1. Quel est le nombre maximum de chaînes palindromiques de longueur 3 ?
2. Comment pouvons-nous garder une trace des caractères apparus à gauche d'une position donnée ?

Solution :

Nous pouvons utiliser un algorithme efficace qui exploite le suivi des caractères de préfixe et de suffixe pour compter toutes les sous-séquences palindromiques valides.

Approche

1. Piste des caractères de préfixe :
   Utilisez un tableau pour stocker l'ensemble de caractères rencontrés à gauche de chaque position dans la chaîne. Cela aidera à vérifier efficacement si un caractère peut former la première partie d'une sous-séquence palindromique.

2. Piste des caractères de suffixe :
   Utilisez un autre tableau pour stocker l'ensemble de caractères rencontrés à droite de chaque position dans la chaîne. Cela aidera à vérifier efficacement si un personnage peut former la troisième partie d'une sous-séquence palindromique.

3. Compter les sous-séquences palindromiques :
   Pour chaque caractère de la chaîne, considérez-le comme le caractère central d'un palindrome de longueur 3. Vérifiez toutes les combinaisons valides de caractères de préfixe et de suffixe pour déterminer des palindromes uniques.

4. Résultats du magasin :
   Utilisez un jeu de hachage pour stocker des sous-séquences palindromiques uniques, en garantissant l'absence de doublons.

Implémentons cette solution en PHP : 1930. Sous-séquences palindromiques uniques de longueur 3

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

// Test cases
echo countPalindromicSubsequence("aabca") . PHP_EOL; // Output: 3
echo countPalindromicSubsequence("adc") . PHP_EOL;   // Output: 0
echo countPalindromicSubsequence("bbcbaba") . PHP_EOL; // Output: 4
?>

Explication:

1. Tableau de préfixes :

   • Pour chaque caractère à la position i, le préfixe[i] stocke tous les caractères distincts rencontrés avant l'index i.

2. Tableau de suffixes :

   • Pour chaque caractère en position i, le suffixe[i] stocke tous les caractères distincts rencontrés après l'index i.

3. Caractère du milieu :

   • Considérez chaque personnage comme le milieu du palindrome. Pour chaque combinaison de caractères préfixe et suffixe qui correspond au caractère du milieu, formez un palindrome de longueur 3.

4. Carte de hachage :

   • Utilisez un tableau associatif ($uniquePalindromes) pour stocker des palindromes uniques, en vous assurant que les doublons ne sont pas comptés.

Complexité

• Complexité temporelle : O(n)

  • Parcourir la chaîne deux fois pour calculer les tableaux de préfixes et de suffixes.
  • Un troisième parcours vérifie les sous-séquences palindromiques valides.

• Complexité spatiale : O(n)

  • Pour les tableaux de préfixes et de suffixes.

Sortir

Le code produit les résultats corrects pour les exemples donnés :

• Entrée : "aabca" → Sortie : 3
• Entrée : "adc" → Sortie : 0
• Entrée : "bbcbaba" → Sortie : 4

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!