LC: 358. Rearrange String k Distance Apart
https://leetcode.com/problems/rearrange-string-k-distance-apart/
358. Rearrange String k Distance Apart
Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".
Example 1:
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.Example 2:
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.Example 3:
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least a distance of 2 from each other.Constraints:
1 <= s.length <= 3 * 105sconsists of only lowercase English letters.0 <= k <= s.length
358. Rearrange String k Distance Apart:
The Essence:
Der ausgewählte Buchstabe soll nicht vor mindestens k Stellen vorkommen. Daher müssen wir entweder den nächsten gültigen Index für jedes Zeichen mittels eines Arrays speichern oder die Zeichenfolge von Anfang an mit der Länge k in Schichten aufteilen. Wir sollen immer das Zeichen mit der höchsten Anzahl verwenden, so dass sie am Ende nicht übrig bleiben, ohne gestellt zu werden.
Details:
Der Problemlöser kann auf unser entsprechendes PR für weitere Erläuterung sowie Implementierung verweisen:
Solutions:
Default Code:
Last updated