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 * 10^5s consists of only lowercase English letters.0 <= k <= s.length
The description was taken from https://leetcode.com/problems/rearrange-string-k-distance-apart/.
#O(N(Log N)) Time, O(N) Space
class Solution:
def rearrangeString(self, s: str, k: int) -> str:
if k == 0:
return s
heap, output, seen = [], [], {}
cycle_back = []
for char in s:
if char not in seen:
seen[char] = -1
else:
seen[char] -= 1
if len(seen) < k:
return "" for char in seen:
heapq.heappush(heap, (seen[char], char))
while heap:
if len(heap) < k and heap[0][0] < -1:
return ""
for _ in range(min(k, len(heap))):
count, char = heapq.heappop(heap)
output.append(char)
if count == -1:
continue
cycle_back.append((count+1, char))
while cycle_back:
heapq.heappush(heap, cycle_back.pop())
return "".join(output)
This question is identical to Task Scheduler.
Similar to that problem, this problem will require a greedy solution, a solution where we would sort the input and handle the most costly tasks first. In this case, the costly tasks will be the characters with the greatest frequency, as they will be the ones more likely to overlap with each other.
What we will do is count the frequency of each character, then put the characters and frequencies in a max heap. From there, we will pop the characters off in the window given. The Pigeonhole Principle is something we will be looking out for to determine if the string can be formed. If the window of characters we are placing characters from the string into is less than k, and the most frequent character still has a frequency greater than one, then we have more characters than indices in which case, we will return an empty string. Otherwise, we will continue until the string is filled.
First off, if there is no spacing required, then we can just return the initial string.
if k == 0:
return s
If none of those cases are true, we will initialize a heap, an output array to form the string, and a hashmap to count the frequency of each character from the input string.
heap, output, seen = [], [], {}
We will also need a list to keep the characters we place into the string so that they don't immediately get cycled back into the heap because they will ruin the spacing in the output.
cycle_back = []
Let's count the frequency of each character.
We will increment by negative values so that the most frequent characters will be the smallest values at the top of the heap. That is how we create a makeshift max-heap from a min-heap in Python.
for char in s:
if char not in seen:
seen[char] = -1
else:
seen[char] -= 1
If the length of the string is less than the character spacing required, then we can't form a string due to the Pigeonhole Principle. If that is the case, we will return an empty string.
if len(seen) < k:
return ""
Otherwise, we will push each character into the heap with its frequency. The frequency will be first so that it is what the heap sorts on.
for char in seen:
heapq.heappush(heap, (seen[char], char))
Now we will begin placing the characters from the heap into the output.
while heap:
Before placing any characters we need to check the window size and the count of the most frequent characters.
If we are toward the end of placing the characters and have a window size less than the spacing required but we also have a character at the top of the heap that still has more values we need to place, we won't be able to form a valid string. We will end up running out of characters to place to fill the padding and then placing the most frequent character back into the window.
We will have more windows to fill than unique characters so two non-unique characters will have to be placed in the same window.
if len(heap) < k and heap[0][0] < -1:
return ""
Other than that, the rest is fairly straightforward.
We will place characters in the minimum between the distance required, or the count of characters we have left if we are toward the end of the output string.
for _ in range(min(k, len(heap))):
count, char = heapq.heappop(heap)
output.append(char)
If the count goes to zero then we won't need to cycle the character back in. If it doesn't, we will decrement the count of the character and append it to the cycle_back array which we will empty back into the heap once the loop has broken and we are done placing characters in the current window.
if count == -1:
continue
cycle_back.append((count+1, char))
Once the loop has broken, we will cycle back the characters and frequencies into the array.
while cycle_back:
heapq.heappush(heap, cycle_back.pop())
When the heap is empty, if we hadn't returned an empty string, then the current string is valid in spacing so we will join the characters into a string and return it.
return "".join(output)