Konstruieren Sie eine Zeichenfolge mit Wiederholungsbegrenzung

2182. Konstruieren Sie eine Zeichenfolge mit Wiederholungsbegrenzung

Schwierigkeit:Mittel

Themen: Hash-Tabelle, String, Greedy, Heap (Prioritätswarteschlange), Zählen

Sie erhalten eine Zeichenfolge s und ein ganzzahliges Wiederholungslimit. Konstruieren Sie eine neue Zeichenfolge „repeatLimitedString“ unter Verwendung der Zeichen von s, sodass kein Buchstabe mehr alsrepeatLimit-mal in einer Reihe vorkommt. Sie müssen nicht alle Zeichen aus s.

Gib den lexikografisch größtenrepeatLimitedString zurück, der möglich ist.

Eine Zeichenfolge a ist lexikographisch größer als eine Zeichenfolge b, wenn an der ersten Position, an der sich a und b unterscheiden, Zeichenfolge a einen Buchstaben enthält, der später im Alphabet erscheint als der entsprechende Buchstabe in b. Wenn sich die ersten Mindestzeichen (a.length, b.length) nicht unterscheiden, ist die längere Zeichenfolge die lexikographisch größere.

Beispiel 1:

• Eingabe: s = "cczazcc", repeatLimit = 3
• Ausgabe: „zzcccac“
• Erklärung: Wir verwenden alle Zeichen von s, um den repeatLimitedString „zzcccac“ zu konstruieren.
  • Der Buchstabe „a“ kommt höchstens einmal hintereinander vor.
  • Der Buchstabe „c“ erscheint höchstens dreimal hintereinander.
  • Der Buchstabe „z“ kommt höchstens 2 Mal hintereinander vor.
  • Daher kommt kein Buchstabe öfter als „repeatLimit“-Mal hintereinander vor und die Zeichenfolge ist ein gültiger „repeatLimitedString“.
  • Der String ist der lexikographisch größte mögliche RepeatLimitedString, daher geben wir „zzcccac“ zurück.
  • Beachten Sie, dass die Zeichenfolge „zzcccca“ lexikographisch größer ist, der Buchstabe „c“ jedoch mehr als dreimal hintereinander vorkommt, sodass es sich nicht um einen gültigen repeatLimitedString handelt.

Beispiel 2:

• Eingabe: s = "aababab", repeatLimit = 2
• Ausgabe: „bbabaa“
• Erklärung: Wir verwenden nur einige der Zeichen von s, um den repeatLimitedString „bbabaa“ zu erstellen.
  • Der Buchstabe „a“ kommt höchstens 2 Mal hintereinander vor.
  • Der Buchstabe „b“ kommt höchstens 2 Mal hintereinander vor.
  • Daher kommt kein Buchstabe öfter als „repeatLimit“-Mal hintereinander vor und die Zeichenfolge ist ein gültiger „repeatLimitedString“.
  • Die Zeichenfolge ist die lexikografisch größte mögliche Wiederholungszeichenfolge, daher geben wir „bbabaa“ zurück.
  • Beachten Sie, dass die Zeichenfolge „bbabaaa“ lexikographisch größer ist, der Buchstabe „a“ jedoch mehr als zweimal hintereinander vorkommt, sodass es sich nicht um einen gültigen RepeatLimitedString handelt.

Einschränkungen:

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

Hinweis:

1. Beginnen Sie mit dem Aufbau der Zeichenfolge in absteigender Reihenfolge der Zeichen.
2. Wenn das Wiederholungslimit erreicht ist, wählen Sie das nächstgrößere Zeichen aus.

Lösung:

Wir verwenden einen gierigen Ansatz, um lexikografisch größere Zeichen zu priorisieren und gleichzeitig sicherzustellen, dass kein Zeichen nacheinander das Wiederholungslimit überschreitet. Der Ansatz verwendet eine Prioritätswarteschlange (maximaler Heap), um Zeichen in lexikographisch absteigender Reihenfolge zu verarbeiten und stellt sicher, dass kein Zeichen öfter als die Wiederholungslimit-Zeiten hintereinander erscheint.

Lösungserklärung

1. Zeichen zählen: Zählen Sie die Häufigkeit jedes Zeichens in der Zeichenfolge mithilfe eines Arrays.
2. Max. Heap: Verwenden Sie einen maximalen Heap (Prioritätswarteschlange), um Zeichen in absteigender lexikografischer Reihenfolge zu sortieren und zu extrahieren.
3. Gierige Konstruktion:
   • Fügen Sie das größte verfügbare Zeichen bis zur Wiederholungsgrenze hinzu.
   • Wenn das Wiederholungslimit für das aktuelle Zeichen erreicht ist, wechseln Sie zum nächstgrößeren Zeichen, fügen Sie es einmal ein und fügen Sie dann das erste Zeichen zur weiteren Verwendung erneut in den Heap ein.
4. Edge Handling: Korrekt verwalten, wenn ein Zeichen nicht weiter verwendet werden kann.

Lassen Sie uns diese Lösung in PHP implementieren: 2182. Konstruieren Sie eine Zeichenfolge mit Wiederholungsbegrenzung

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

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>Häufigkeitszählung:</strong></p>

<ul>
<li>Durchlaufen Sie die Zeichenfolge s, um das Vorkommen jedes Zeichens zu zählen.</li>
<li>Speichern Sie die Frequenz in einem assoziativen Array $freq.</li>
</ul>
</li>
<li>
<p><strong>In absteigender Reihenfolge sortieren:</strong></p>

<ul>
<li>Verwenden Sie krsort(), um die Zeichen nach ihrer lexikografischen Reihenfolge in <strong>absteigender</strong> Reihenfolge zu sortieren.</li>
</ul>
</li>
<li>
<p><strong>Erstellen Sie das Ergebnis:</strong></p>

<ul>
<li>Fügen Sie fortlaufend das lexikografisch größte Zeichen ($char) an die Ergebniszeichenfolge an.</li>
<li>Wenn ein Zeichen sein Wiederholungslimit erreicht, stoppen Sie vorübergehend das Anhängen.</li>
<li>Verwenden Sie eine temporäre Warteschlange, um Zeichen zu speichern, deren Anzahl noch übrig ist, die aber vorübergehend übersprungen werden.</li>
</ul>
</li>
<li>
<p><strong>Handle-Wiederholungslimit:</strong></p>

<ul>
<li>Wenn das aktuelle Zeichen das Wiederholungslimit erreicht hat, verwenden Sie das lexikografisch nächstgrößte Zeichen aus der Warteschlange.</li>
<li>Fügen Sie das vorherige Zeichen wieder in die Frequenzkarte ein, um es später weiterzuverarbeiten.</li>
</ul>
</li>
<li>
<p><strong>Edge Cases:</strong></p>
<ul>
<li>Charaktere verbrauchen möglicherweise zunächst nicht ihre volle Anzahl.</li>
<li>Nachdem ein Ersatzzeichen aus der Warteschlange verarbeitet wurde, wird die Verarbeitung des aktuellen Zeichens fortgesetzt.</li>
</ul>
</li>
</ol>

<h3>
  
  
  <strong>Wie es funktioniert</strong>
</h3>

<ol>
<li>
<strong>Zeichenanzahl</strong>: $freq verfolgt das Vorkommen aller Zeichen.</li>
<li>
<strong>Max. Heap</strong>: SplPriorityQueue wird als maximaler Heap verwendet, bei dem Zeichen nach ihrem ASCII-Wert (absteigende Reihenfolge) priorisiert werden.</li>
<li>
<strong>Saitenaufbau</strong>:

<ul>
<li>Wenn das aktuelle Zeichen sein Wiederholungslimit erreicht hat, rufen Sie das nächstgrößere Zeichen ab.</li>
<li>Verwenden Sie das nächstgrößere Zeichen einmal und fügen Sie das vorherige Zeichen für die zukünftige Verwendung wieder in den Heap ein.</li>
</ul>
</li>
<li>
<strong>Endergebnis</strong>: Die resultierende Zeichenfolge ist die lexikographisch größte Zeichenfolge, die die RepeatLimit-Einschränkung erfüllt.</li>
</ol>

<h3>
  
  
  <strong>Beispiel-Anleitung</strong>
</h3>

<p><strong>Eingabe:</strong><br><br>
s = "cczazcc", repeatLimit = 3</p>

<p><strong>Schritte:</strong></p>

<ol>
<li><p>Häufigkeitszählung:<br><br>
['a' => 1, 'c' => 4, 'z' => 2]</p></li>
<li><p>In absteigender Reihenfolge sortieren:<br><br>
['z' => 2, 'c' => 4, 'a' => 1]</p></li>
<li>
<p>Fügen Sie Zeichen unter Beachtung von „repeatLimit:“ hinzu:</p>

<ul>
<li>’z’ → „zz“ anhängen (Z-Anzahl = 0)</li>
<li>3 Mal „c“ anhängen → „zzccc“ (c count = 1)</li>
<li>Fügen Sie 'a' → "zzccca" an (a count = 0)</li>
<li>Verbleibendes 'c' anhängen → „zzcccac“</li>
</ul>
</li>
</ol>

<p><strong>Ausgabe:</strong> „zzcccac“</p>

<h3>
  
  
  <strong>Zeitkomplexität</strong>
</h3>

<ul>
<li>
<strong>Zeichenhäufigkeitszählung</strong>: <em><strong>O(n)</strong></em>, wobei <em><strong>n</strong></em> die Länge der Zeichenfolge ist.</li>
<li>
<strong>Heap-Operationen</strong>: <em><strong>O(26 log 26)</strong></em>, da der Heap bis zu 26 Zeichen enthalten kann.</li>
<li>
<strong>Gesamtkomplexität</strong>: <em><strong>O(n 26 log 26) ≈ O(n)</strong></em>.</li>
</ul>

<h3>
  
  
  <strong>Weltraumkomplexität</strong>
</h3>

<ul>
<li>
<em><strong>O(26)</strong></em> für das Frequenzarray.</li>
<li>
<em><strong>O(26)</strong></em> für den Heap.</li>
</ul>

<h3>
  
  
  <strong>Testfälle</strong>
</h3>



<pre class="brush:php;toolbar:false"><?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>

Edge Cases

1. s enthält nur ein eindeutiges Zeichen (z. B. „aaaaaaa“, repeatLimit = 2): Die Ausgabe enthält nur so viele Zeichen, wie hintereinander zulässig sind.
2. repeatLimit = 1: Die Ausgabe wechselt zwischen den verfügbaren Zeichen.
3. Alle Zeichen in s sind eindeutig: Die Ausgabe wird in absteigender Reihenfolge sortiert.

Diese Implementierung funktioniert effizient innerhalb der Einschrä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 vonKonstruieren Sie eine Zeichenfolge mit Wiederholungsbegrenzung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!