Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 358 with 20 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 358 # by problem number
lcpy gen -s rearrange_string_k_distance_apart # by problem name
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 "".
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least a distance of 2 from each other.
1 <= s.length <= 3 * 10^5s consists of only lowercase English letters.0 <= k <= s.lengthfrom collections import Counter, deque
from heapq import heapify, heappop, heappush
class Solution:
# Time: O(n log n)
# Space: O(n)
def rearrange_string(self, s: str, k: int) -> str:
cnt = Counter(s)
pq = [(-v, c) for c, v in cnt.items()]
heapify(pq)
q = deque()
ans: list[str] = []
while pq:
v, c = heappop(pq)
ans.append(c)
q.append((v + 1, c))
if len(q) >= k:
e = q.popleft()
if e[0]:
heappush(pq, e)
return "" if len(ans) < len(s) else "".join(ans)
| Time | Space |
|---|---|
| O(n log n) | O(n) |