Finden Sie die längste spezielle Teilzeichenfolge, die dreimal vorkommt

2981. Finden Sie die längste spezielle Teilzeichenfolge, die dreimal vorkommt I

Schwierigkeit:Mittel

Themen:Hash-Tabelle, String, Binäre Suche, Schiebefenster, Zählen

Sie erhalten eine Zeichenfolge s, die aus englischen Kleinbuchstaben besteht.

Eine Zeichenfolge wird speziell genannt, wenn sie nur aus einem einzigen Zeichen besteht. Beispielsweise ist die Zeichenfolge „abc“ nichts Besonderes, wohingegen die Zeichenfolgen „ddd“, „zz“ und „f“ etwas Besonderes sind.

Gibt die Länge des längsten speziellen Teilstrings von s zurück, der mindestens dreimal vorkommt, oder -1, wenn kein spezieller Teilstring mindestens dreimal vorkommt.

Eine Teilzeichenfolge ist eine zusammenhängende nicht leere Folge von Zeichen innerhalb einer Zeichenfolge.

Beispiel 1:

• Eingabe: s = "aaaa"
• Ausgabe: 2
• Erklärung: Der längste spezielle Teilstring, der dreimal vorkommt, ist „aa“: Teilstrings „aaaa“, „aaaa“ und „aaaa“.
  • Es kann gezeigt werden, dass die maximal erreichbare Länge 2 beträgt.

Beispiel 2:

• Eingabe: s = "abcdef"
• Ausgabe: -1
• Erklärung: Es gibt keinen speziellen Teilstring, der mindestens dreimal vorkommt. Geben Sie daher -1 zurück.

Beispiel 3:

• Eingabe: s = "abcdef"
• Ausgabe: 1
• Erklärung: Der längste spezielle Teilstring, der dreimal vorkommt, ist „a“: Teilstrings „abcaba“, „abcaba“ und „abcaba“.
  • Es kann gezeigt werden, dass die maximal erreichbare Länge 1 beträgt.

Einschränkungen:

• 3 <= s.length <= 50
• s besteht nur aus englischen Kleinbuchstaben.

Hinweis:

1. Die Einschränkungen sind gering.
2. Brute-Force-Überprüfung aller Teilzeichenfolgen.

Lösung:

Aufgrund der geringen Einschränkungen von s (Länge bis zu 50) können wir einen Brute-Force-Ansatz verwenden. Wir werden:

1. Iterieren Sie über mögliche Längen von Teilzeichenfolgen (von der längsten zur kürzesten).
2. Überprüfen Sie alle Teilzeichenfolgen der angegebenen Länge und zählen Sie deren Vorkommen.
3. Wenn eine Teilzeichenfolge mindestens dreimal vorkommt, prüfen Sie, ob sie etwas Besonderes ist (aus einem wiederholten Zeichen besteht).
4. Gibt die Länge des längsten solchen Teilstrings zurück. Wenn kein Teilstring die Bedingungen erfüllt, geben Sie -1 zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2981. Finden Sie die längste spezielle Teilzeichenfolge, die dreimal vorkommt I

  
  
  Erläuterung:




Äußere Schleife: Wir iterieren über die möglichen Längen von Teilzeichenfolgen, beginnend mit der längsten. Dadurch wird sichergestellt, dass wir den längsten speziellen Teilstring zurückgeben, sobald wir ihn finden.

Schiebefenster: Für jede Teilstringlänge verwenden wir einen Schiebefensteransatz, um alle Teilstrings dieser Länge zu extrahieren.

Teilstrings zählen: Wir verwenden ein assoziatives Array ($countMap), um das Vorkommen jedes Teilstrings zu speichern und zu zählen.

Spezielles prüfen: Eine Hilfsfunktion isSpecial prüft, ob die Teilzeichenfolge nur aus einem wiederholten Zeichen besteht.

Rückgabe des Ergebnisses: Wenn ein gültiger Teilstring gefunden wird, geben wir seine Länge zurück; andernfalls geben wir -1 zurück.



  
  
  Komplexität




Zeitkomplexität: O(n3) im schlimmsten Fall, weil wir:


Iterieren Sie über n Teilstringlängen.
Extrahieren Sie O(n) Teilzeichenfolgen für jede Länge.
Überprüfen Sie, ob jeder Teilstring etwas Besonderes ist, was O(n) Zeit dauert.



Raumkomplexität: O(n2) aufgrund der Teilstring-Zählkarte.


Dieser Brute-Force-Ansatz ist angesichts der Einschränkungen machbar (n <= 50).

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 vonFinden Sie die längste spezielle Teilzeichenfolge, die dreimal vorkommt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!