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(|\Sigma|), 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.

Rearrange String k Distance Apart — LeetCode 358 Python Solution

HardLeetCode PremiumGreedyHash TableStringCountingSortingHeap (Priority Queue)

Problem: #358
Pattern: 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

Python

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

Measure	Complexity
Time	O(n \log n), where n is the length of the string
Space	O(\|\Sigma\|), where \|\Sigma\| is the size of the character set, which is 26 in this problem auxiliary

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.

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(|\Sigma|), 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.