Mindestlänge der Zeichenfolge nach Operationen

3223. Mindestlänge der Zeichenfolge nach Operationen

Schwierigkeit:Mittel

Themen:Hash-Tabelle, String, Zählen

Sie erhalten eine Zeichenfolge s.

Sie können den folgenden Vorgang beliebigmal ausführen:

• Wählen Sie einen Index i in der Zeichenfolge, so dass links vom Index i mindestens ein Zeichen steht, das gleich s[i] ist, und mindestens ein Zeichen rechts ist das auch gleich s[i].
• Löschen Sie das nächste Zeichen links vom Index i, das gleich s[i] ist.
• Löschen Sie das nächste Zeichen rechts vom Index i, das gleich s[i] ist.

Gib die minimale Länge der endgültigen Zeichenfolge s zurück, die Sie erreichen können.

Beispiel 1:

• Eingabe: s = "abaacbcbb"
• Ausgabe: 5
• Erklärung: Wir führen die folgenden Vorgänge durch:
  • Wählen Sie Index 2 und entfernen Sie dann die Zeichen bei den Indizes 0 und 3. Die resultierende Zeichenfolge ist s = "bacbcbb".
  • Wählen Sie Index 3 und entfernen Sie dann die Zeichen bei den Indizes 0 und 5. Die resultierende Zeichenfolge ist s = "acbcb".

Beispiel 2:

• Eingabe: s = "aa"
• Ausgabe: 2
• Erklärung: Wir können keine Operationen ausführen, daher geben wir die Länge der ursprünglichen Zeichenfolge zurück.

Einschränkungen:

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

Hinweis:

1. Für die endgültige Antwort ist nur die Häufigkeit jedes Zeichens von Bedeutung.
2. Wenn ein Zeichen weniger als dreimal vorkommt, können wir keinen Prozess damit durchführen.
3. Angenommen, es gibt ein Zeichen, das mindestens dreimal in der Zeichenfolge vorkommt, können wir zwei dieser Zeichen wiederholt löschen, bis höchstens noch zwei Vorkommen davon übrig sind.

Lösung:

Wir müssen uns auf die Häufigkeit jedes Zeichens in der Zeichenfolge konzentrieren. Hier ist der Lösungsansatz:

Ansatz:

1. Zeichenhäufigkeiten zählen:

   • Verwenden Sie eine Häufigkeitstabelle, um zu zählen, wie oft jedes Zeichen in der Zeichenfolge vorkommt.

2. Zeichen mit Häufigkeit >= 3 reduzieren:

   • Wenn ein Zeichen dreimal oder öfter vorkommt, können wir zwei davon wiederholt löschen, bis nur noch zwei Vorkommen übrig sind.

3. Berechnen Sie die Mindestlänge:

   • Summieren Sie die verbleibende Anzahl aller Zeichen, nachdem Sie die Häufigkeit reduziert haben.

Lassen Sie uns diese Lösung in PHP implementieren: 3223. Mindestlänge der Zeichenfolge nach Operationen


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

// Example 1
$s1 = "abaacbcbb";
echo "Input: $s1\n";
echo "Output: " . minimumLength($s1) . "\n";

// Example 2
$s2 = "aa";
echo "Input: $s2\n";
echo "Output: " . minimumLength($s2) . "\n";
?>

Nach dem Login kopieren

Erläuterung:

1. Frequenzzählung:

   • Durchlaufen Sie die Zeichenfolge und erhöhen Sie für jedes Zeichen die Anzahl im $frequenz-Array.

2. Reduzierung der Zeichen:

   • Überprüfen Sie für jedes Zeichen im $ Frequency-Array, ob seine Anzahl 3 oder mehr beträgt. Wenn ja, reduzieren Sie es auf höchstens 2.

3. Berechnen Sie das Ergebnis:

   • Summieren Sie die Werte im $frequenz-Array, um die minimal mögliche Länge der Zeichenfolge zu erhalten.

Beispielhafte Vorgehensweise:

Beispiel 1:

• Eingabe: s = "abaacbcbb"
• Häufigkeiten: ['a' => 3, 'b' => 4, 'c' => 2]
• Nach der Reduktion:
  • 'a' => 2 (reduziert von 3),
  • 'b' => 2 (reduziert von 4),
  • 'c' => 2 (keine Reduzierung erforderlich).
• Mindestlänge: 2 2 2 = 6.

Beispiel 2:

• Eingabe: s = "aa"
• Häufigkeiten: ['a' => 2]
• Keine Reduzierung erforderlich, da kein Zeichen eine Häufigkeit von 3 oder mehr hat.
• Mindestlänge: 2.

Komplexität:

1. Zeitkomplexität:

   • Zählhäufigkeiten: O(n), wobei n die Länge der Zeichenfolge ist.
   • Reduktion: O(1) (konstante Zeit, da es nur 26 Kleinbuchstaben gibt).
   • Summierungsfrequenzen: O(1).
   • Insgesamt: O(n).

2. Weltraumkomplexität:

   • O(1), da das Frequenzarray höchstens 26 Einträge hat.

Diese Lösung ist effizient und funktioniert gut innerhalb der Problembeschränkungen.

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 vonMindestlänge der Zeichenfolge nach Operationen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!