Einzigartige längenalindromische Teilsequenzen

1930. Einzigartige palindromische Subsequenzen der Länge 3

Schwierigkeit:Mittel

Themen: Hash-Tabelle, String, Bitmanipulation, Präfixsumme

Gibt bei einer gegebenen Zeichenfolge s die Anzahl der einzigartigen Palindrome der Länge drei zurück, die eine Teilfolge von s.

sind

Beachten Sie, dass selbst wenn es mehrere Möglichkeiten gibt, dieselbe Teilsequenz zu erhalten, diese immer noch nur einmal gezählt wird.

Ein Palindrom ist eine Zeichenfolge, die vorwärts und rückwärts dasselbe liest.

Eine Teilsequenz einer Zeichenfolge ist eine neue Zeichenfolge, die aus der ursprünglichen Zeichenfolge generiert wird, wobei einige Zeichen (es können auch keine sein) gelöscht werden, ohne die relative Reihenfolge der verbleibenden Zeichen zu ändern.

• Zum Beispiel ist „ace“ eine Teilfolge von „abcde“.

Beispiel 1:

• Eingabe: s = "aabca"
• Ausgabe: 3
• Erklärung: Die 3 palindromischen Teilsequenzen der Länge 3 sind:
  • „aba“ (Teilfolge von „aabca“)
  • „aaa“ (Teilfolge von „aabca“)
  • „aca“ (Teilfolge von „aabca“)

Beispiel 2:

• Eingabe: s = "adc"
• Ausgabe: 0
• Erklärung:Es gibt keine palindromischen Teilsequenzen der Länge 3 in „adc“.

Beispiel 3:

• Eingabe: s = "bbcbaba"
• Ausgabe: 4
• Erklärung: Die 4 palindromischen Teilsequenzen der Länge 3 sind:
  • „bbb“ (Teilfolge von „bbcbaba“)
  • „bcb“ (Teilfolge von „bbcbaba“)
  • „bab“ (Teilfolge von „bbcbaba“)
  • „aba“ (Teilfolge von „bbcbaba“)

Einschränkungen:

• 3 5
• s besteht nur aus englischen Kleinbuchstaben.

Hinweis:

1. Was ist die maximale Anzahl palindromischer Zeichenfolgen der Länge 3?
2. Wie können wir den Überblick über die Zeichen behalten, die links von einer bestimmten Position erschienen sind?

Lösung:

Wir können einen effizienten Algorithmus verwenden, der die Verfolgung von Präfix- und Suffixzeichen nutzt, um alle gültigen palindromischen Teilsequenzen zu zählen.

Ansatz

1. Track-Präfixzeichen:
   Verwenden Sie ein Array, um den Satz von Zeichen zu speichern, die links von jeder Position in der Zeichenfolge angetroffen werden. Dies hilft bei der effizienten Überprüfung, ob ein Zeichen den ersten Teil einer palindromischen Teilsequenz bilden kann.

2. Suffixzeichen verfolgen:
   Verwenden Sie ein anderes Array, um den Zeichensatz zu speichern, der rechts von jeder Position in der Zeichenfolge vorkommt. Dies hilft bei der effizienten Überprüfung, ob ein Zeichen den dritten Teil einer palindromischen Teilsequenz bilden kann.

3. Palindromische Subsequenzen zählen:
   Betrachten Sie jedes Zeichen in der Zeichenfolge als das mittlere Zeichen eines Palindroms der Länge 3. Suchen Sie nach allen gültigen Kombinationen von Präfix- und Suffixzeichen, um eindeutige Palindrome zu ermitteln.

4. Ergebnisse speichern:
   Verwenden Sie einen Hash-Satz, um eindeutige palindromische Teilsequenzen zu speichern und sicherzustellen, dass es keine Duplikate gibt.

Lassen Sie uns diese Lösung in PHP implementieren: 1930. Einzigartige palindromische Subsequenzen der Länge 3

<?php /**
 * @param String $s
 * @return Integer
 */
function countPalindromicSubsequence($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo countPalindromicSubsequence("aabca") . PHP_EOL; // Output: 3
echo countPalindromicSubsequence("adc") . PHP_EOL;   // Output: 0
echo countPalindromicSubsequence("bbcbaba") . PHP_EOL; // Output: 4
?>

Erläuterung:

1. Präfix-Array:

   • Für jedes Zeichen an Position i speichert Präfix[i] alle unterschiedlichen Zeichen, die vor Index i angetroffen werden.

2. Suffix-Array:

   • Für jedes Zeichen an Position i speichert Suffix[i] alle unterschiedlichen Zeichen, die nach Index i vorkommen.

3. Mittelzeichen:

   • Betrachten Sie jedes Zeichen als die Mitte des Palindroms. Bilden Sie für jede Kombination aus Präfix- und Suffixzeichen, die mit dem mittleren Zeichen übereinstimmt, ein Palindrom der Länge 3.

4. Hash-Map:

   • Verwenden Sie ein assoziatives Array ($uniquePalindromes), um eindeutige Palindrome zu speichern und sicherzustellen, dass Duplikate nicht gezählt werden.

Komplexität

• Zeitkomplexität: O(n)

  • Zweimaliges Durchlaufen der Zeichenfolge, um die Präfix- und Suffix-Arrays zu berechnen.
  • Ein dritter Durchlauf prüft gültige palindromische Teilsequenzen.

• Raumkomplexität: O(n)

  • Für Präfix- und Suffix-Arrays.

Ausgabe

Der Code liefert die korrekten Ergebnisse für die angegebenen Beispiele:

• Eingabe: „aabca“ → Ausgabe: 3
• Eingabe: „adc“ → Ausgabe: 0
• Eingabe: „bbcbaba“ → Ausgabe: 4

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 vonEinzigartige längenalindromische Teilsequenzen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!