Löschen Sie Zeichen, um eine ausgefallene Zeichenfolge zu erstellen

1957. Löschen Sie Zeichen, um eine ausgefallene Zeichenfolge zu erstellen

Schwierigkeit:Einfach

Themen:String

Eine ausgefallene Zeichenfolge ist eine Zeichenfolge, bei der keine drei aufeinanderfolgenden Zeichen gleich sind.

Löschen Sie bei einer gegebenen Zeichenfolge s die minimum mögliche Anzahl an Zeichen aus s, um es ausgefallen zu machen.

Gibt die letzte Zeichenfolge nach dem Löschen zurück. Es kann gezeigt werden, dass die Antwort immer einzigartig sein wird.

Beispiel 1:

• Eingabe: s = "leeetcode"
• Ausgabe: „leetcode“
• Erklärung: Entfernen Sie ein „e“ aus der ersten Gruppe von „e“, um „leetcode“ zu erstellen. Keine drei aufeinanderfolgenden Zeichen sind gleich, also geben Sie „leetcode“ zurück.

Beispiel 2:

• Eingabe: s = "aaabaaaa"
• Ausgabe: „aabaa“
• Erklärung: Entfernen Sie ein „a“ aus der ersten Gruppe von „a“, um „aabaaaa“ zu erstellen. Entfernen Sie zwei „a“ aus der zweiten Gruppe von „a“, um „aabaa“ zu erstellen. Keine drei aufeinanderfolgenden Zeichen sind gleich, also geben Sie „aabaa“ zurück.

Beispiel 3:

• Eingabe: s = "aab"
• Ausgabe: „aab“
• Erklärung: Keine drei aufeinanderfolgenden Zeichen sind gleich, also geben Sie „aab“ zurück.

Einschränkungen:

• 1 <= s.length <= 10⁵
• s besteht nur aus englischen Kleinbuchstaben.

Hinweis:

1. Wie lösche ich Zeichen optimal, wenn drei oder mehr aufeinanderfolgende Zeichen gleich sind?
2. Wenn drei oder mehr aufeinanderfolgende Zeichen gleich sind, behalten Sie zwei davon und löschen Sie den Rest.

Lösung:

Wir müssen sicherstellen, dass in der letzten Zeichenfolge keine drei aufeinanderfolgenden Zeichen gleich sind. Wir durchlaufen die Eingabezeichenfolge und erstellen eine neue „ausgefallene“ Zeichenfolge, indem wir die beiden vorherigen Zeichen im Auge behalten. Wenn ein drittes aufeinanderfolgendes Zeichen mit den letzten beiden übereinstimmt, überspringen wir es. Andernfalls fügen wir es der Ausgabe hinzu.

Lassen Sie uns diese Lösung in PHP implementieren: 1957. Löschen Sie Zeichen, um eine ausgefallene Zeichenfolge zu erstellen

  
  
  Erläuterung:




Variablen initialisieren:



$result: Dadurch wird die endgültige „ausgefallene“ Zeichenfolge gespeichert.



Durch den String iterieren:


Überprüfen Sie für jedes Zeichen, ob es mit den letzten beiden Zeichen im Ergebnis ein Trio bildet.
Wenn dies der Fall ist, überspringen Sie das Hinzufügen zu $result.
Wenn nicht, fügen Sie es zu $result hinzu.



Ergebnis zurückgeben:

Die $result-Zeichenfolge enthält jetzt keine drei aufeinanderfolgenden identischen Zeichen.





  
  
  Komplexitätsanalyse




Zeitkomplexität: O(n), wobei n die Länge der Eingabezeichenfolge ist, wie wir Verarbeiten Sie jedes Zeichen einmal.

Raumkomplexität: O(n), zum Speichern der Ausgabezeichenfolge.


Diese Lösung erfüllt die Einschränkungen effizient und stellt sicher, dass die endgültige Zeichenfolge keine drei aufeinanderfolgenden identischen Zeichen enthält.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonLöschen Sie Zeichen, um eine ausgefallene Zeichenfolge zu erstellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!