Anzahl der Teilzeichenfolgen mit der gleichen Anzahl an Klein- und Großbuchstaben

Bei diesem Problem müssen wir die Gesamtzahl der Zeichenfolgen zählen, die in der angegebenen Zeichenfolge die gleiche Anzahl an Klein- und Großbuchstaben enthalten. Der naive Weg, dieses Problem zu lösen, besteht darin, alle Teilzeichenfolgen zu finden und die Gesamtzahl der Teilzeichenfolgen mit der gleichen Anzahl an Klein- und Großbuchstaben zu zählen.

Ein effizienter Ansatz besteht darin, das Subarray-Summationsproblem zu verwenden. Wir können Kleinbuchstaben als -1 und Großbuchstaben als +1 behandeln und lernen beide Möglichkeiten zur Lösung des Problems kennen.

Problemstellung – Wir erhalten eine Zeichenfolge str, die Klein- und Großbuchstaben enthält. Wir müssen die Gesamtzahl der Teilzeichenfolgen zählen, die die gleiche Anzahl an Klein- und Großbuchstaben enthalten.

Beispiel

Eingabe – str = ‚TutOR‘

Ausgabe – 4

Erklärung–Wir können 4 Teilzeichenfolgen erhalten, nämlich „Tu“, „TutO“, „tO“ und „utOR“, die die gleiche Anzahl an Klein- und Großbuchstaben enthalten

Eingabe – str = ‚abcd‘

Ausgabe – 0

Erklärung – Wir können keinen Teilstring erhalten, der die gleichen Klein- und Großbuchstaben enthält, da der String nur Kleinbuchstaben enthält

Eingabe – str = ‚XYz‘

Ausgabe– 1

Erklärung – Wir können nur die Teilzeichenfolge „Yz“ abrufen.

Methode 1

Dies ist eine naive Art, das Problem zu lösen. Wir werden drei verschachtelte Schleifen verwenden, um alle Teilzeichenfolgen einer bestimmten Zeichenfolge zu finden. Wir prüfen, ob jeder Teilstring die gleiche Anzahl an Klein- und Großbuchstaben enthält. Wenn ja, erhöhen wir die Anzahl um 1.

Algorithmus

• Definieren Sie die Variable „cnt“ und initialisieren Sie sie auf Null.

• Verwenden Sie eine for-Schleife, um die Zeichenfolge zu durchlaufen

• In der Schleife definieren Sie die Variablen „upperCase“ und „lowerCase“ und initialisieren sie mit Nullen

• Fügen Sie eine weitere verschachtelte Schleife in Ihren Code ein, um die Zeichenfolge beginnend mit dem i-ten Index zu iterieren. Auf diese Weise können wir einen Teilstring vom i-ten Index zum j-ten Index erhalten

• Wenn das Zeichen in einer verschachtelten Schleife ein Großbuchstabe ist, erhöhen Sie den Wert der Großbuchstabenvariablen um 1. Andernfalls erhöhen Sie den Wert der Kleinbuchstabenvariablen um 1.

• Wenn die Werte der Variablen „upperCase“ und „lowerCase“ gleich sind, erhöhen Sie den Wert von „cnt“ um 1.

• Gibt den Wert von „cnt“ zurück.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

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

Zeitliche Komplexität – O(N^2), da wir verschachtelte Schleifen verwenden, um alle Teilzeichenfolgen zu finden.

Raumkomplexität – O(1), weil wir konstanten Raum verwenden.

Methode 2

Bei dieser Methode optimieren wir den Code der oben genannten Methode, um die zeitliche Komplexität der Lösung zu verbessern. Wir behandeln Großbuchstaben als +1 und Kleinbuchstaben als -1. Darüber hinaus verwenden wir eine Kartendatenstruktur, um die Häufigkeit der Präfixsumme zu speichern. Wenn wir feststellen, dass die Präfixsumme gleich Null ist oder mit einer in der Karte gespeicherten Präfixsumme übereinstimmt, können wir den Zählwert erhöhen.

Algorithmus

• Definieren Sie eine „Summen“-Karte, die ganze Zahlen als Schlüssel-Wert-Paare enthält.

• Definieren Sie die Variable „cnt“ und initialisieren Sie sie auf Null, um die Gesamtzahl der Teilzeichenfolgen mit gleichen Klein- und Großbuchstaben zu speichern. Definieren Sie gleichzeitig die Variable „current“, um das Präfix und

zu speichern

• Beginnen Sie mit dem Durchlaufen der Saite. Wenn das aktuelle Zeichen ein Großbuchstabe ist, erhöhen Sie die Variable „aktuell“ um 1. Andernfalls verringern Sie das „aktuelle“ Zeichen um 1.

• Wenn der Wert von „current“ 0 ist, finden wir den Teilstring und erhöhen den Wert von „cnt“ um 1

• Überprüfen Sie, ob die Karte „aktuell“ als Schlüssel enthält. Wenn ja, ermitteln Sie den Wert und fügen Sie ihn zur Variablen „cnt“ hinzu.

• Erhöhen Sie den Wert des „aktuellen“ Schlüssels in der Karte um 1.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Um das Problem besser zu verstehen. Lassen Sie uns die Beispieleingabe debuggen, die „TutOR“ ist.

Wenn wir also mit der Iteration der Zeichenfolge beginnen, wird der Wert von „current“ am ersten Index zu 0. Erhöhen Sie also den Wert von „cnt“ um 1. Beim dritten Index geht er wieder auf Null. Erhöhen Sie also den Wert von „cnt“ um 1 auf 2. Wir haben vorher auch 0 erhalten, also ist es in der Karte vorhanden und wir müssen diesen Wert zu „cnt“ hinzufügen. Es wird also 3.

Wenn wir den 4. Index erreichen, ist der Wert der „aktuellen“ Variablen 1 und wir erhalten ihn wieder, genau wie wir ihn beim 0. Index erhalten haben. Fügen Sie also „1“ zu „cnt“ hinzu.

Die Grundlogik besteht darin, dass wir die Teilzeichenfolge erhalten, wenn „aktuell“ 0 ist. Wenn wir den Wert von „aktuell“ erneut erhalten, können wir die Zeichenfolge zwischen den beiden Indizes erhalten, da „aktuell – aktuell“ Null ist.

<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>

Ausgabe

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

Zeitkomplexität – O(N), da wir die Zeichenfolge nur einmal durchlaufen.

Raumkomplexität – O(N), weil wir eine Karte verwenden, um die Präfixsumme zu speichern. Im schlimmsten Fall, wenn die Zeichenfolge nur Klein- oder Großbuchstaben enthält, benötigen wir O(N)-Leerzeichen.

Wir haben gelernt, zwei verschiedene Methoden anzuwenden, um das oben genannte Problem zu lösen. Die erste Methode verwendet verschachtelte Schleifen, um alle Zeichenfolgen zu überprüfen, während die zweite Methode hinsichtlich der Zeitkomplexität effizienter ist als die erste, aber mehr Platz beansprucht.

Das obige ist der detaillierte Inhalt vonAnzahl der Teilzeichenfolgen mit der gleichen Anzahl an Klein- und Großbuchstaben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!