Comptez le nombre de sous-chaînes constituées d'un seul caractère distinct

Dans cet article, nous aborderons le problème du comptage du nombre de sous-chaînes constituées de caractères uniques distincts dans une chaîne donnée. Nous explorerons un algorithme efficace pour résoudre ce problème et fournirons du code C++ pour l'implémenter.

Énoncé du problème

Étant donné une chaîne S, la tâche consiste à compter le nombre de sous-chaînes constituées de caractères uniques distincts.

Par exemple, si la chaîne d'entrée est "aaaaa", la sortie doit être 15 car il existe 15 sous-chaînes composées de caractères uniques distincts. Les sous-chaînes sont "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "aaa" , "aaa", "aaaa", "aaaa", "aaaa".

Algorithme

Nous pouvons résoudre ce problème avec une complexité temporelle linéaire. Nous pouvons parcourir la chaîne d'entrée et garder une trace du caractère actuel et de la longueur de la sous-chaîne actuelle. Chaque fois qu'un nouveau caractère est rencontré ou que la fin de la chaîne est atteinte, nous pouvons compter le nombre de sous-chaînes pouvant être formées par le caractère actuel et la longueur de la sous-chaîne actuelle.

Voici un algorithme étape par étape pour résoudre ce problème -

• Initialisez le nombre et la lentille à 1.

• Parcourez la chaîne S de l'index 1 à n-1.

• Si le caractère actuel est le même que le caractère précédent, len est augmenté de 1.

• Si le caractère actuel est différent du caractère précédent, ajoutez (len*(len+1))/2 pour compter et réinitialisez len ​​à 1.

• Compte de retour.

Prenons la chaîne "aaaaa" comme exemple pour comprendre l'algorithme -

• Initialisez le nombre et la lentille à 1.

• Itérer sur une chaîne de l'index 1 à n-1 :

• À l'index 1, le caractère actuel est le même que le caractère précédent, donc len est augmenté de 1.

• À l'index 2, le caractère actuel est le même que le caractère précédent, donc len est augmenté de 1.

• À l'index 3, le caractère actuel est le même que le caractère précédent, donc len est augmenté de 1.

• À l'index 4, le caractère actuel est le même que le caractère précédent, donc len est augmenté de 1.

• Nous avons atteint la fin de la chaîne, alors ajoutez (len*(len+1))/2 pour compter. Nombre = Nombre + (5*(5+1))/2 = 15.

• Compte de retour.

Implémentation C++

C'est le code C++ qui implémente l'algorithme ci-dessus -

Exemple

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string S) {
   int n = S.length();
   int count = 1, len = 1;
   for (int i = 1; i < n; i++) {
      if (S[i] == S[i-1]) {
         len++;
      } else {
         count += (len*(len+1))/2;
         len = 1;
      }
   }
   count += (len*(len+1))/2;
   return count-1;
}

int main() {
   string S = "aaaaa";
   int count = countSubstrings(S);
   cout << count << endl;
   return 0;
}

Sortie

15

Conclusion

Dans cet article, nous avons discuté du problème du comptage du nombre de sous-chaînes constituées de caractères uniques distincts dans une chaîne donnée. Nous fournissons un algorithme efficace pour résoudre ce problème en complexité temporelle linéaire et l'implémentons en C++. Ce problème peut également être résolu en utilisant d'autres techniques, mais l'algorithme ci-dessus fournit

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!