Trouver la sous-chaîne spéciale la plus longue qui apparaît trois fois I

2981. Trouver la sous-chaîne spéciale la plus longue qui apparaît trois fois I

Difficulté :Moyen

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

Vous recevez une chaîne s composée de lettres anglaises minuscules.

Une chaîne est dite spéciale si elle est composée d'un seul caractère. Par exemple, la chaîne "abc" n'est pas spéciale, alors que les chaînes "ddd", "zz" et "f" sont spéciales.

Renvoie la longueur de la sous-chaîne spéciale la plus longue de s qui apparaît au moins trois fois, ou -1 si aucune sous-chaîne spéciale n'apparaît au moins trois fois.

Une sous-chaîne est une séquence contiguë non vide de caractères au sein d'une chaîne.

Exemple 1 :

• Entrée : s = "aaaa"
• Sortie : 2
• Explication : La sous-chaîne spéciale la plus longue qui apparaît trois fois est "aa" : les sous-chaînes "aaaa", "aaaa" et "aaaa".
  • On peut montrer que la longueur maximale réalisable est de 2.

Exemple 2 :

• Entrée : s = "abcdef"
• Sortie : -1
• Explication : Il n'existe aucune sous-chaîne spéciale qui apparaît au moins trois fois. Renvoyez donc -1.

Exemple 3 :

• Entrée : s = "abcdef"
• Sortie : 1
• Explication : La sous-chaîne spéciale la plus longue qui apparaît trois fois est "a": les sous-chaînes "abcaba", "abcaba" et "abcaba".
  • On peut montrer que la longueur maximale réalisable est de 1.

Contraintes :

• 3 <= s.length <= 50
• s se compose uniquement de lettres anglaises minuscules.

Indice :

1. Les contraintes sont faibles.
2. Force brute vérifiant toutes les sous-chaînes.

Solution :

Nous pouvons utiliser une approche par force brute en raison des petites contraintes de s (longueur jusqu'à 50). Nous allons :

1. Parcourez les longueurs possibles de sous-chaînes (de la plus longue à la plus courte).
2. Vérifiez toutes les sous-chaînes de la longueur donnée et comptez leurs occurrences.
3. Si une sous-chaîne apparaît au moins trois fois, vérifiez si elle est spéciale (constituée d'un caractère répété).
4. Renvoie la longueur de la sous-chaîne la plus longue. Si aucune sous-chaîne ne satisfait aux conditions, renvoie -1.

Implémentons cette solution en PHP : 2981. Trouver la sous-chaîne spéciale la plus longue qui apparaît trois fois I

  
  
  Explication:




Boucle extérieure : Nous parcourons les longueurs possibles des sous-chaînes, en commençant par la plus longue. Cela garantit que nous renvoyons la sous-chaîne spéciale la plus longue dès que nous la trouvons.

Fenêtre coulissante : Pour chaque longueur de sous-chaîne, nous utilisons une approche de fenêtre coulissante pour extraire toutes les sous-chaînes de cette longueur.

Comptage des sous-chaînes : Nous utilisons un tableau associatif ($countMap) pour stocker et compter les occurrences de chaque sous-chaîne.

Checking Special : Une fonction d'assistance isSpecial vérifie si la sous-chaîne est composée d'un seul caractère répété.

Renvoi du résultat : Si une sous-chaîne valide est trouvée, nous renvoyons sa longueur ; sinon, on renvoie -1.



  
  
  Complexité




Complexité temporelle : O(n3) dans le pire des cas car nous :


Parcourir n longueurs de sous-chaînes.
Extraire O(n) sous-chaînes pour chaque longueur.
Vérifiez si chaque sous-chaîne est spéciale, ce qui prend O(n) temps.



Complexité spatiale : O(n2) en raison de la carte de comptage de sous-chaînes.


Cette approche par force brute est réalisable compte tenu des contraintes (n <= 50).

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!