HardNo. 0358LeetCode Premium
Rearrange String k Distance Apart — LeetCode 358 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Hash Table, String, Counting, Sorting, Heap (Priority Queue)
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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
- Input
- s = "aabbcc", k = 3
- Output
- "abcabc"
- Explanation
- The same letters are at least a distance of 3 from each other.
Python solution
class Solution:
def rearrangeString(self, s: str, k: int) -> str:
cnt = Counter(s)
pq = [(-v, c) for c, v in cnt.items()]
heapify(pq)
q = deque()
ans = []
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)Complexity
- Time
- O(n log n), where n is the length of the string
- Space · auxiliary
- O(|Σ|), where |Σ| is the size of the character set, which is 26 in this problem
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 358. Rearrange String k Distance Apart is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0767 | Reorganize String | Medium |
| 0451 | Sort Characters By Frequency | Medium |
| 0621 | Task Scheduler | Medium |
| 0692 | Top K Frequent Words | Medium |
| 1054 | Distant Barcodes | Medium |
| 2182 | Construct String With Repeat Limit | Medium |
Frequently asked questions
- How hard is LeetCode 358. Rearrange String k Distance Apart?
LeetCode 358. Rearrange String k Distance Apart is rated Hard on LeetCode.
- What is the time complexity of LeetCode 358. Rearrange String k Distance Apart?
The Python solution on this page runs in O(n log n), where n is the length of the string.
- What is the space complexity of LeetCode 358. Rearrange String k Distance Apart?
The Python solution on this page uses O(|Σ|), where |\Sigma| is the size of the character set, which is 26 in this problem auxiliary space.
- What topics does LeetCode 358. Rearrange String k Distance Apart cover?
LeetCode 358. Rearrange String k Distance Apart is tagged Greedy, Hash Table, String, Counting, Sorting and Heap (Priority Queue) on LeetCode.
- Is LeetCode 358. Rearrange String k Distance Apart a premium problem?
Yes. LeetCode 358. Rearrange String k Distance Apart is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.