Nombre de sous-chaînes avec le même nombre de lettres minuscules et majuscules

Dans ce problème, nous devons compter le nombre total de chaînes contenant le même nombre de caractères minuscules et majuscules dans la chaîne donnée. La manière naïve de résoudre ce problème consiste à rechercher toutes les sous-chaînes et à compter le nombre total de sous-chaînes avec le même nombre de caractères minuscules et majuscules.

Une approche efficace consiste à utiliser un problème de sommation de sous-tableaux. Nous pouvons traiter les caractères minuscules comme -1 et les caractères majuscules comme +1, et nous apprendrons les deux manières de résoudre le problème.

Énoncé du problème- On nous donne une chaîne str qui contient des caractères alphabétiques minuscules et majuscules. Nous devons compter le nombre total de sous-chaînes contenant le même nombre de caractères minuscules et majuscules.

Exemple

Entrée – str = 'TutOR'

Sortie – 4

Explication–Nous pouvons obtenir 4 sous-chaînes, qui sont 'Tu', 'TutO', 'tO' et 'utOR', qui contiennent le même nombre de lettres minuscules et majuscules

Entrée – str = 'abcd'

Sortie – 0

Explication – Nous ne pouvons obtenir aucune sous-chaîne contenant les mêmes caractères minuscules et majuscules car la chaîne ne contient que des caractères minuscules

Entrée – str = 'XYz'

Sortie– 1

Explication - Nous ne pouvons obtenir que la sous-chaîne 'Yz'.

Méthode 1

C'est une façon naïve de résoudre le problème. Nous utiliserons 3 boucles imbriquées pour trouver toutes les sous-chaînes d'une chaîne donnée. Nous vérifierons si chaque sous-chaîne contient le même nombre de caractères minuscules et majuscules. Si tel est le cas, nous incrémentons le décompte de 1.

Algorithme

• Définissez la variable 'cnt' et initialisez-la à zéro.

• Utilisez une boucle for pour parcourir la chaîne

• Dans la boucle, définissez les variables 'upperCase' et 'lowerCase' et initialisez-les avec des zéros

• Ajoutez une autre boucle imbriquée dans votre code pour parcourir la chaîne à partir du ième index. De cette façon, nous pouvons obtenir une sous-chaîne du i-ème index au j-ème index

• Dans une boucle imbriquée, si le caractère est en majuscule, augmentez la valeur de la variable majuscule de 1. Sinon, augmentez la valeur de la variable minuscule de 1.

• Si les valeurs des variables 'upperCase' et 'lowerCase' sont égales, augmentez la valeur de 'cnt' de 1.

• Renvoyer la valeur de « cnt ».

Exemple

Exemple

#include <iostream>
using namespace std;
// function to find the total number of substrings that have an equal number of lowercase and uppercase characters
int totalSubStrings(string &str, int N){
   // variable to store the count.
   int cnt = 0;
   for (int i = 0; i < str.length(); i++){
      // variable to store the count of upper and lower case characters
      int upperCase = 0;
      int lowerCase = 0;
      for (int j = i; j < str.length(); j++){
         // If the character is in uppercase, then increment upperCase
         if (str[j] >= 'A' && str[j] <= 'Z')
            upperCase++;
         else
            lowerCase++;
         // If the count of uppercase and lowercase characters is equal, then increment cnt
            if (upperCase == lowerCase)
               cnt++;
         }
      }
   return cnt;
}
int main(){
   string str = "TutOR";
   cout << "The total number of substrings that have equal lowercase and uppercase characters is " << totalSubStrings(str, str.length());
   return 0;
}

Sortie

The total number of substrings that have equal lowercase and uppercase characters is 4

Complexité temporelle - O(N^2) car nous utilisons des boucles imbriquées pour trouver toutes les sous-chaînes.

Complexité spatiale - O(1) car nous utilisons un espace constant.

Méthode 2

Dans cette méthode, nous optimiserons le code de la méthode ci-dessus pour améliorer la complexité temporelle de la solution. Nous traitons les caractères majuscules comme +1 et les caractères minuscules comme -1. De plus, nous utiliserons une structure de données cartographiques pour stocker la fréquence de la somme des préfixes. Si nous constatons que la somme des préfixes est égale à zéro, ou identique à toute somme de préfixes stockée dans la carte, nous pouvons incrémenter la valeur du comptage.

Algorithme

• Définissez une carte "somme" contenant des entiers sous forme de paires clé-valeur.

• Définissez la variable 'cnt' et initialisez-la à zéro pour stocker le nombre total de sous-chaînes avec des caractères minuscules et majuscules égaux. En même temps, définissez la variable 'current' pour stocker le préfixe et

• Commencez à parcourir la chaîne. Si le caractère actuel est une lettre majuscule, augmentez la variable 'current' de 1. Sinon, décrémentez le caractère « actuel » de 1.

• Si la valeur de « current » est 0, nous trouvons la sous-chaîne et augmentons la valeur de « cnt » de 1

• Vérifiez si la carte contient "current" comme clé. Si c'est le cas, récupérez sa valeur et ajoutez-la à la variable "cnt".

• Augmentez la valeur de la clé "actuelle" dans la carte de 1.

Exemple

Exemple

Pour mieux comprendre le problème. Déboguons l'exemple d'entrée, qui est « TutOR ».

Ainsi, lorsque nous commencerons à itérer la chaîne, la valeur de « actuel » deviendra 0 au premier index. Alors, augmentez la valeur de « cnt » de 1. Encore une fois, au troisième indice, il ira à zéro. Donc, augmentez la valeur de « cnt » de 1 pour devenir 2. Nous avons également obtenu 0 auparavant, il est donc présent sur la carte et nous devons ajouter cette valeur à « cnt ». Cela deviendra donc 3.

Lorsque nous atteignons le 4ème indice, la valeur de la variable « actuelle » sera 1 et nous l'obtiendrons à nouveau comme nous l'avons eu au 0ème indice. Ajoutez donc « 1 » à « cnt ».

La logique de base est que si « actuel » est égal à 0, nous obtenons la sous-chaîne. Si nous obtenons à nouveau la valeur de « courant », nous pouvons obtenir la chaîne entre les deux indices car « courant – courant » est nul.

<span style="font-size: 13.125px;">#include <iostream>
#include <unordered_map>
using namespace std;

// function to find the total number of substrings that have an equal number of lowercase and uppercase characters
int totalSubStrings(string &str, int N){
    // map to store the frequency of sums generated by the difference in the count of lowercase and uppercase characters
    unordered_map<int, int> sum;
    // to store the count of substrings that have an equal number of lowercase and uppercase characters
    int cnt = 0;
    // current sum
    int current = 0;
    for (int i = 0; i < N; i++){
        // If the character is uppercase, then increment the current value
        if (str[i] >= 'A' and str[i] <= 'Z'){
            current++;
        }
        // Otherwise, decrement the current value
        else
            current--;
        // If the current value is 0, then a substring is found. So, increment the count by 1
        if (current == 0)
            cnt++;
        // If the current value exists in the map, then update the cnt by adding the frequency of the current value
        if (sum[current]){
            cnt += (sum[current]);
        }
        // Increment the frequency of the current value in the map
        sum[current]++;
    }
    return cnt;
}
int main(){
    string str = "TutOR";
    cout << "The total number of substrings that have equal lowercase and uppercase characters is " << totalSubStrings(str, str.length());
    return 0;
}</span>

Sortie

The total number of substrings that have equal lowercase and uppercase characters is 4

Complexité temporelle - O(N) puisque nous ne parcourons la chaîne qu'une seule fois.

Complexité spatiale – O(N) car nous utilisons une carte pour stocker la somme des préfixes. Dans le pire des cas, lorsque la chaîne contient tous les caractères minuscules ou majuscules, nous avons besoin d'un espace O(N).

Nous avons appris à utiliser deux méthodes différentes pour résoudre le problème ci-dessus. La première méthode utilise des boucles imbriquées pour vérifier toutes les chaînes, tandis que la deuxième méthode est plus efficace que la première en termes de complexité temporelle, mais prend plus de place.

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!