Construire des cordes K Palindrome

1400. Construire des cordes K Palindrome

Difficulté :Moyen

Sujets : Table de hachage, chaîne, gourmande, comptage

Étant donné une chaîne s et un entier k, retournez true si vous pouvez utiliser tous les caractères de s pour construire k chaînes palindromes ou false sinon.

Exemple 1 :

• Entrée : s = "annabelle", k = 2
• Sortie : vrai
• Explication : Vous pouvez construire deux palindromes en utilisant tous les caractères de s.
  • Quelques constructions possibles "anna" "elble", "anbna" "elle", "anellena" "b"

Exemple 2 :

• Entrée : s = "leetcode", k = 3
• Sortie : faux
• Explication : Il est impossible de construire 3 palindromes en utilisant tous les caractères de s.

Exemple 3 :

• Entrée : s = "vrai", k = 4
• Sortie : vrai
• Explication : La seule solution possible est de mettre chaque caractère dans une chaîne distincte.

Contraintes :

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

Indice :

1. Si la longueur < k nous ne pouvons pas construire k chaînes à partir de s et la réponse est fausse.
2. Si le nombre de caractères impairs est > k alors le nombre minimum de chaînes palindromes que nous pouvons construire est > k et la réponse est fausse.
3. Sinon, vous pouvez construire exactement k chaînes de palindrome et la réponse est vraie (pourquoi ?).

Solution :

Nous devons considérer les points suivants :

Observations clés :

1. Caractéristiques du Palindrome :

   • Un palindrome est une chaîne qui lit la même chose vers l'avant et vers l'arrière.
   • Pour un palindrome de longueur paire, tous les caractères doivent apparaître un nombre pair de fois.
   • Pour un palindrome de longueur impaire, tous les caractères sauf un doivent apparaître un nombre pair de fois (le caractère qui apparaît un nombre impair de fois sera au centre).

2. Conditions nécessaires :

   • Si la longueur de s est inférieure à k, il est impossible de former k chaînes, alors retournez false.
   • Le nombre total de caractères qui apparaissent un nombre impair de fois doit être d'au plus k pour former k palindromes. En effet, chaque palindrome peut avoir au plus un caractère avec un nombre impair (le caractère central pour les palindromes de longueur impaire).

Approche:

1. Comptez la fréquence de chaque caractère de la chaîne.
2. Comptez combien de caractères ont une fréquence impaire.
3. Si le nombre de fréquences impaires dépasse k, renvoie false (car il est impossible de former k palindromes).

Implémentons cette solution en PHP : 1400. Construire des cordes K Palindrome


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

// Test cases
var_dump(canConstruct("annabelle", 2)); // Output: true
var_dump(canConstruct("leetcode", 3)); // Output: false
var_dump(canConstruct("true", 4));      // Output: true
?>

Explication:

1. Frequency Count : Nous utilisons un tableau associatif $freq pour compter les occurrences de chaque caractère dans la chaîne.
2. Compte impair : Nous vérifions combien de caractères ont des occurrences impaires. Cela nous aidera à déterminer si nous pouvons former des palindromes.
3. Vérification de condition : Si le nombre de caractères aux fréquences impaires est supérieur à k, il est impossible de former k palindromes, nous renvoyons donc faux. Sinon, on renvoie vrai.

Complexité temporelle :

• Le comptage des fréquences prend O(n), où n est la longueur de la chaîne.
• La vérification des fréquences impaires prend O(m), où m est le nombre de caractères distincts (au plus 26 pour les lettres anglaises minuscules).
• La complexité temporelle globale est O(n m), ce qui se simplifie en O(n) dans ce cas.

Cas extrêmes :

1. Si k est supérieur à la longueur de s, nous renvoyons faux.
2. Si tous les caractères ont des fréquences paires, nous pouvons toujours former un palindrome, donc le résultat dépend de la possibilité ou non de k.

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!