Nehmen Sie K von jedem Zeichen von links und rechts

2516. Nimm K von jedem Zeichen von links und rechts

Schwierigkeit:Mittel

Themen:Hash-Tabelle, String, Schiebefenster

Sie erhalten eine Zeichenfolge s, die aus den Zeichen „a“, „b“ und „c“ und einer nicht negativen Ganzzahl k besteht. Jede Minute können Sie entweder das Zeichen ganz links von s oder das Zeichen ganz rechts von s.

nehmen

Geben Sie die Mindestanzahl Minuten zurück, die Sie benötigen, um mindestens k von jedem Zeichen zu nehmen, oder geben Sie -1 zurück, wenn es nicht möglich ist, k von jedem Zeichen zu nehmen Zeichen.

Beispiel 1:

• Eingabe: s = "aabaaaacaabc", k = 2
• Ausgabe: 8
• Erklärung: Nehmen Sie drei Zeichen von links von s. Sie haben jetzt zwei „a“-Zeichen und ein „b“-Zeichen.
  • Nehmen Sie fünf Zeichen von rechts von s. Sie haben jetzt vier „a“-Zeichen, zwei „b“-Zeichen und zwei „c“-Zeichen.
  • Insgesamt werden 3 5 = 8 Minuten benötigt.
  • Es kann nachgewiesen werden, dass 8 die minimal benötigte Anzahl an Minuten ist.

Beispiel 2:

• Eingabe: s = "a", k = 1
• Ausgabe: -1
• Erklärung:Es ist nicht möglich, ein „b“ oder „c“ zu nehmen, also geben Sie -1 zurück.

Einschränkungen:

• 1 <= s.length <= 10⁵
• s besteht nur aus den Buchstaben „a“, „b“ und „c“.
• 0 <= k <= s.length

Hinweis:

1. Beginnen Sie damit, die Häufigkeit jedes Zeichens zu zählen und zu prüfen, ob dies möglich ist.
2. Wenn Sie x Zeichen von der linken Seite übernehmen, wie viele Zeichen müssen Sie dann mindestens von der rechten Seite übernehmen? Finden Sie dies für alle Werte von x im Bereich 0 ≤ x ≤ s.length.
3. Verwenden Sie einen Zwei-Punkte-Ansatz, um zu vermeiden, dass dieselben Informationen mehrmals berechnet werden.

Lösung:

Wir können eine Schiebefenstertechnik mit zwei Zeigern verwenden, um die Mindestanzahl von Minuten zu ermitteln, die erforderlich sind, um mindestens k jedes Zeichens ('a', 'b', 'c') sowohl links als auch rechts vom zu entnehmen Zeichenfolge.

Problemaufschlüsselung:

• Wir erhalten eine Zeichenfolge s, die nur „a“, „b“ und „c“ enthält.
• Wir müssen mindestens k Vorkommen jedes Zeichens nehmen, entweder von den ganz linken oder ganz rechten Zeichen der Zeichenfolge.
• Wir müssen die Mindestanzahl an Minuten ermitteln, die erforderlich sind, um dies zu erreichen, oder -1 zurückgeben, wenn dies nicht möglich ist.

Ansatz:

1. Erstprüfungen:

   • Wenn k == 0, können wir direkt 0 zurückgeben, da keine Zeichen erforderlich sind.
   • Wenn k die Anzahl der Vorkommen eines beliebigen Zeichens in der Zeichenfolge überschreitet, wird sofort -1 zurückgegeben.

2. Frequenzzählung:

   • Wir müssen zählen, wie oft „a“, „b“ und „c“ in der Zeichenfolge s vorkommen, um sicherzustellen, dass es überhaupt möglich ist, k von jedem Zeichen zu erfassen.

3. Schiebefenster-Technik:

   • Verwenden Sie einen Schiebefenster-Ansatz mit zwei Zeigern (links und rechts).
   • Behalten Sie zwei Zeiger bei und schieben Sie sie von beiden Enden der Zeichenfolge, um die erforderlichen Zeichen zu sammeln.
   • Berechnen Sie für jede Anzahl von Zeichen, die von links entnommen werden, die Mindestanzahl von Zeichen, die von rechts entnommen werden müssen, um die Anforderung zu erfüllen.

4. Optimierung:

   • Anstatt die Zeichenanzahl für jedes Fenster wiederholt neu zu berechnen, können wir die Zeichenanzahl verfolgen, während wir das Fenster erweitern oder verkleinern.

Lassen Sie uns diese Lösung in PHP implementieren: 2516. Nimm K von jedem Zeichen von links und rechts

  
  
  Erläuterung:




Ersteinrichtung:


Wir zählen die Vorkommen von „a“, „b“ und „c“ in der gesamten Zeichenfolge, um sicherzustellen, dass mindestens k von jedem Zeichen erfasst werden können.
Wenn eine Zeichenanzahl weniger als k beträgt, wird -1 zurückgegeben.



Schiebefenster:


Wir verwenden zwei Zeiger (links und rechts), um an beiden Enden ein Schiebefenster zu erstellen.
Wir erweitern das Fenster, indem wir den rechten Zeiger bewegen und erhöhen die Anzahl der gefundenen Zeichen.
Sobald wir mindestens k von jedem Zeichen im aktuellen Fenster haben, versuchen wir, das Fenster von links her zu verkleinern, um die Anzahl der Minuten (belegte Zeichen) zu minimieren.



Zeit minimieren:


Wir verfolgen die erforderliche Mindestanzahl an Minuten, indem wir die Größe des Fensters jedes Mal vergleichen, wenn wir k Zeichen aller Art sammeln.





  
  
  Zeitkomplexität:



Das Zählen von Zeichen erfordert zunächst O(n).
Der Schiebefenstervorgang erfordert O(n), da sich sowohl der linke als auch der rechte Zeiger einmal über die Zeichenfolge bewegen.
Die Gesamtzeitkomplexität beträgt O(n).



  
  
  Randfälle:



Wenn k == 0, gebe 0 zurück.
Wenn es unmöglich ist, k von jedem Zeichen zu nehmen, geben Sie -1 zurück.


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 vonNehmen Sie K von jedem Zeichen von links und rechts. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!